Structured Scaling of AI Discovery Across Diverse Scientific Domains — part 6/12

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

We first characterize a single trajectory. Set α = 1 / β \alpha=1/\beta . Dividing the transition probability in Definition .2 by β \beta gives p d ​ ( t ) = α + y d ​ ( t − 1 ) D ​ α + t − 1 . \displaystyle p_{d}(t)=\frac{\alpha+y_{d}(t-1)}{D\alpha+t-1}. (12) This is the standard symmetric Pólya urn with initial mass α \alpha on each of the D D dimensions. Therefore, the vector of refinement counts after L L steps has the Dirichlet-multinomial law y ⁡ ( L ) ∼ DM ⁡ ( L , α , … , α ) . \displaystyle y(L)\sim\operatorname{DM}(L;\alpha,\ldots,\alpha). (13) Equivalently, it admits the mixture representation P = ( P 1 , … , P D ) \displaystyle P=(P_{1},\ldots,P_{D}) ∼ Dirichlet ⁡ ( α , … , α ) , \displaystyle\sim\operatorname{Dirichlet}(\alpha,\ldots,\alpha), (14) y ⁡ ( L ) | P \displaystyle y(L)\mid P ∼ Multinomial ⁡ ( L , P ) . \displaystyle\sim\operatorname{Multinomial}(L,P). (15) Hence, if L , r → ∞ L,r\to\infty with r / L → γ r/L\to\gamma , then y ⁡ ( L ) L ⇒ P , \displaystyle\frac{y(L)}{L}\Rightarrow P, (16) and the single-trajectory failure probability satisfies, for every γ ∈ ( 0 , 1 / D ) \gamma\in(0,1/D) , F L ​ ( r ) := Pr ⁡ ( min d ∈ [ D ] ⁡ y d ​ ( L ) < r ) → F ⁡ ( γ ) := Pr ⁡ ( min d ∈ [ D ] ⁡ P d < γ ) . \displaystyle F_{L}(r):=\Pr\!\left(\min_{d\in[D]}y_{d}(L)<r\right)\to F(\gamma):=\Pr\!\left(\min_{d\in[D]}P_{d}<\gamma\right). (17) The function F F depends only on D D and β \beta and is continuous on ( 0 , 1 / D ) (0,1/D) . Moreover, 0 < F ⁡ ( γ ) < 1 0<F(\gamma)<1 for γ ∈ ( 0 , 1 / D ) \gamma\in(0,1/D) , F ⁡ ( γ ) → 0 F(\gamma)\to 0 as γ ↓ 0 \gamma\downarrow 0 , and F ⁡ ( γ ) → 1 F(\gamma)\to 1 as γ ↑ 1 / D \gamma\uparrow 1/D . Near zero, the beta marginal of any coordinate gives F ⁡ ( γ ) = Ω ⁡ ( γ α ) F(\gamma)=\Omega(\gamma^{\alpha}) , and hence − γ ​ log ⁡ F ​ ( γ ) → 0 -\gamma\log F(\gamma)\to 0 as γ ↓ 0 \gamma\downarrow 0 .

For C C independent trajectories, the failure event is that every trajectory fails, so P fail ​ ( L , C ) = F L ​ ( r ) C . \displaystyle P_{\mathrm{fail}}(L,C)=F_{L}(r)^{C}. (18) Ignoring the integer rounding, we write L = r / γ L=r/\gamma with γ ∈ ( 0 , 1 / D ) \gamma\in(0,1/D) . The smallest number of independent trajectories needed to achieve asymptotic failure probability at most ϵ \epsilon is C ⁡ ( γ ) = log ⁡ ϵ log ⁡ F ⁡ ( γ ) ​ ( 1 + o ⁡ ( 1 ) ) = log ⁡ ( 1 / ϵ ) − log ⁡ F ⁡ ( γ ) ​ ( 1 + o ⁡ ( 1 ) ) . \displaystyle C(\gamma)=\frac{\log\epsilon}{\log F(\gamma)}(1+o(1))=\frac{\log(1/\epsilon)}{-\log F(\gamma)}(1+o(1)). (19) The corresponding budget is therefore N ⁡ ( γ ) = L ​ C ​ ( γ ) = r ​ log ⁡ ( 1 / ϵ ) ​ 1 − γ ​ log ⁡ F ​ ( γ ) ​ ( 1 + o ⁡ ( 1 ) ) . \displaystyle N(\gamma)=LC(\gamma)=r\log(1/\epsilon)\frac{1}{-\gamma\log F(\gamma)}(1+o(1)). (20) Minimizing N ⁡ ( γ ) N(\gamma) is equivalent to maximizing G ⁡ ( γ ) = − γ ​ log ⁡ F ⁡ ( γ ) . \displaystyle G(\gamma)=-\gamma\log F(\gamma). (21) The endpoint behavior above implies G ⁡ ( γ ) → 0 G(\gamma)\to 0 as γ ↓ 0 \gamma\downarrow 0 and as γ ↑ 1 / D \gamma\uparrow 1/D , while G ⁡ ( γ ) > 0 G(\gamma)>0 on ( 0 , 1 / D ) (0,1/D) . Thus, by continuity, G G attains a maximum at some γ ⋆ ∈ ( 0 , 1 / D ) \gamma^{\star}\in(0,1/D) , and γ ⋆ \gamma^{\star} depends only on D D and β \beta .

Substituting this structural constant gives L ⋆ = r γ ⋆ ​ ( 1 + o ⁡ ( 1 ) ) = Θ ⁡ ( r ) , C ⋆ = log ⁡ ( 1 / ϵ ) − log ⁡ F ⁡ ( γ ⋆ ) ​ ( 1 + o ⁡ ( 1 ) ) = Θ ⁡ ( log ⁡ 1 ϵ ) . \displaystyle L^{\star}=\frac{r}{\gamma^{\star}}(1+o(1))=\Theta\!\left(r\right),\qquad C^{\star}=\frac{\log(1/\epsilon)}{-\log F(\gamma^{\star})}(1+o(1))=\Theta\!\left(\log\frac{1}{\epsilon}\right). (22) Finally, r = ⌈ log λ ⁡ ( 1 − s ) ⌉ = Θ ⁡ ( log λ ⁡ ( 1 − s ) ) r=\lceil\log_{\lambda}(1-s)\rceil=\Theta(\log_{\lambda}(1-s)) as s → 1 s\to 1 , which proves the claimed allocation scalings. ∎

##### Remark.

The theorem rigorously justifies the effect of independent experiments. This reflects a fundamental asymmetry between the two scaling factors: C C governs the exploration strength, while L L governs exploitation power. This asymmetry is manifested clearly in practice. For instance, on the Second Autocorrelation Inequality, the strongest agent such as Claude-Code with Opus 4.6 plateaued at a score of 0.9438, even with hundreds of refinement steps at a cost of ∼ 100 \sim 100 million tokens and ∼ 500 \sim 500 USD. However, by effectively balancing C C and L L (method specified below), we match this score using the open-source gpt-oss-120b model 2 2 2 Estimated costs for gpt-oss-120b are calculated based on the median pricing from OpenRouter, which is $0.15 per 1M input tokens and $0.60 per 1M output tokens. at a cost of ∼ 60 \sim 60 USD ( 8.3 × 8.3\times gap). More surprisingly, we achieve a SOTA score of 0.9627 by continuously scaling up the evaluation ( ∼ 400 \sim 400 USD), a score that no closed-source model could improve upon. This empirical evidence clearly demonstrates the importance of identifying the correct factor for evaluation scaling.

Having demonstrated how compute should be allocated across multiple refinement trajectories, we turn to the scaling within each trajectory, with a given budget L = N / C L=N/C . At first glance, more refinement steps seem preferable, as each step can leverage feedback from previous attempts. However, this intuition could break down when path dependence is strong ( β \beta is large), when each refinement step further commits the trajectory to its current direction, making it harder to escape suboptimal regions.

##### Local sample size K K .

The preceding analysis motivates a second budget axis: the local sample size K K . While the number of independent trajectories C C mitigates global path dependence by exploring different refinement paths, K K addresses a more local failure mode: an individual refinement proposal may fail to improve the current solution. We model this by assuming that, after a dimension is selected according to the Pólya refinement rule in Definition .2 , the generator produces K K independent refinement proposals for that dimension. Each proposal improves the selected dimension with probability p p , and otherwise leaves it unchanged. The best proposal is then applied. Thus, increasing K K raises the probability that a refinement step results in an actual improvement from p p to 1 − ( 1 − p ) K 1-(1-p)^{K} , but it also reduces the number of sequential refinement steps under a fixed total budget.

We empirically illustrate this trade-off in Figure 1 . We simulate problems parameterized by ( D , λ , β ) (D,\lambda,\beta) under the refinement model in Definition .2 , fixing L = 4096 L=4096 , β = 4 \beta=4 , and C = 32 C=32 independent trajectories, and report the normalized final bottleneck score averaged over 2048 simulations. The results show that moderate values of K K substantially improve performance over purely sequential refinement ( K = 1 ) (K=1) , especially when the improvement probability p p is large enough for local sampling to reliably find a useful proposal. However, very large K K can degrade performance, since allocating more budget to local sampling leaves fewer refinement steps. This confirms that K K should be treated as a trade-off parameter rather than a monotonic source of improvement. We further study this interaction between C C , L L , and K K on real open-ended tasks in Section F .

Together, the total evaluation budget N = C × K × L N=C\times K\times L has been decomposed into three scaling dimensions: global independent trajectories C C , local sample size K K , and the actual refinement depth L = N C ​ K L=\frac{N}{CK} . In short, this section aims to recognize the simple yet effective factors to be scaled, with the evidence below showing that by wisely scaling these parameters, we can achieve state-of-the-art solutions on most problems considered. Arguably, there is clear room for further improvements. For instance, the current budget is divided evenly across each trajectory. Clearly, discarding unsatisfying trajectories on-the-fly and saving budgets for promising trajectories could be helpful. Additionally, one might recognize the fractal structure of C C and L L , both being i.i.d. attempts at different levels. As an analogy, breaking L L sequential refinement steps into smaller segments to couple more complexity might be beneficial. Relevant ablations can be found in Section F .

### D Method Analysis

In this section, we present a comprehensive analysis of our proposed framework. We first investigate its scaling behaviors, demonstrating how systematic expansion of the evaluator-query budget drives continuous performance improvements. Next, we examine the impacts of training, highlighting its ability to enhance both in-domain and out-of-domain discovery capabilities. We then analyze various reward hacking phenomena that emerge when models autonomously exploit vulnerabilities in surrogate evaluators. Finally, we conduct detailed ablation studies to evaluate the individual contributions of core framework components.

#### D.1 Experiments on the Scaling Behavior of SimpleTES

To investigate the scaling behavior of SimpleTES , we explore the impact of key framework parameters: total evaluation budget N N , refinement depth L L , global width C C , and local sample size K K . We aim to reveal how the framework effectively translates increased computational scale into substantial performance improvements. In our ablation studies, we select three representative open-ended tasks—the First Autocorrelation Inequality, the Erdős Minimum-Overlap Problem, and the TriMul task in GPU kernel optimization—to investigate the scalability of SimpleTES .

##### Scalability of global width ( C C ) and refinement depth ( L L ).

First, we scale along the dimensions of global parallel exploration ( C C ) and sequential refinement depth ( L L ). For these experiments, we hold the local sample size constant at K = 32 K=32 . The results are visualized in Figure 2 .

As demonstrated in the heatmaps, SimpleTES exhibits strong and consistent scalability along both the global width ( C C ) and sequential refinement depth ( L L ) axes. The consistent performance improvements observed as L L increases serve as compelling evidence for the efficacy of sequential refinement , demonstrating that iteratively leveraging historical feedback successfully drives targeted enhancements. However, because sequential refinement is inherently path-dependent and prone to saturation around local optima, scaling C C provides a critical and complementary advantage. The robust gains along the C C axis validate the power of parallel exploration: by distributing the evaluation budget across independent trajectories, the framework successfully diversifies the committed histories, effectively mitigating path-dependent bottlenecks and ensuring that later refinements compound upon structurally advantageous foundations.

Furthermore, the heatmaps reveal that the performance benefits derived from scaling C C versus scaling L L are strongly task-dependent. For mathematical discovery tasks like the First Autocorrelation Inequality and the Erdős Minimum-Overlap Problem, scaling the number of parallel chains C C (e.g., up to C = 32 C=32 ) provides a more pronounced advantage at larger scales. Mathematical constructions often require extensive exploration of diverse starting points to discover a promising structural “flash of insight.” Conversely, for the TriMul GPU kernel optimization task, scaling the iteration depth L L drives the most significant performance gains. Kernel optimization heavily relies on complex, step-by-step engineering refinement rather than sudden structural breakthroughs, making deep trajectories (large L L ) essential to systematically tune hardware-specific parameters and iteratively squeeze out peak performance.

##### Scalability of local sample size ( K K ) and refinement depth ( L L ).

Next, we analyze the interaction between depth L L and local sample size K K by fixing the global parallelization at C = 32 C=32 , as illustrated in Figure 3 . Along the depth dimension, performance consistently improves as L L increases across all configurations. This is expected, as deeper chains allow the policy to iteratively exploit feedback and refine the best discovered paradigms.

However, scaling the local sample size K K reveals a highly dynamic, depth-dependent behavior. At shallow chain depths (small L L ), allocating more compute to K K does not yield a consistent monotonic increase in performance. In these early stages, generating a higher-quality node via a larger K K does not necessarily translate to an immediate breakthrough; the solution is still navigating broad structural choices, making the early refinement steps inherently noisy. Yet, this trend is robustly consolidated as the chain deepens. At large values of L L , scaling K K clearly and consistently drives superior final performance, which implies that, while a rigorously selected node might not immediately show a massive score advantage, it establishes a fundamentally higher-quality foundation that is more amenable to continuous improvement. As the chain extends, this early structural advantage compounds, allowing the long-term benefits of local quality control to fully materialize.

##### Scalability of the total evaluation budget ( N N ).

Building upon the previous analysis of the effects of C C , K K and L L , we further investigate the overall scaling behavior as a function of the total evaluation budget N = L × C × K N=L\times C\times K . As illustrated in Figure 4 , SimpleTES demonstrates a remarkably stable performance improvement as the available compute budget scales. This trend highlights a core strength of our framework: it does not merely consume inference tokens, but highly effectively translates an expanded evaluation budget into tangible, systematic performance gains. Crucially, this robust scaling behavior points to an important test-time scaling law for open-ended scientific discovery. It demonstrates that SimpleTES allows researchers to continuously and reliably push past existing performance upper bounds through the allocation of additional evaluation calls.

#### D.2 Experimental Details on Post-Training

In this subsection, we investigate whether post-training methods successfully transform the TES histories into parametric knowledge. For simplicity and training efficiency, we focus on mathematical extremal analysis and combinatorial construction tasks. Specifically, we adopt the Second Autocorrelation Inequality, the Third Autocorrelation Inequality, Circle Packing in a Unit Square with n = 26 n=26 , and Erdős Minimum-Overlap Problem as training tasks. In addition to these tasks, we perform evaluation on 4 held-out tasks, including the First Autocorrelation Inequality, Circle Packing in a Unit Square with n=32, Hadamard Maximum-Determinant Problem of Order 29 29 , and the Sum-Difference Problem. We perform post-training for 6 iterations. For the first training iteration, we collect ∼ \sim 320 trajectories for each task with K = 16 K=16 and L = 100 L=100 and default settings of Φ \Phi in Methods for cold-start. For subsequent iterations, we sample C ^ = 32 \hat{C}=32 trajectories for each task using the same hyperparameters. We adopt the IRFT setting, set the selection ratio R = 10 R=10 for top-performing trajectories in the first 4 iterations and R = 5 R=5 for the last 2 iterations. The number of effective training samples with w = 1 w=1 for each iteration ranges from 8.1K to 10.7K. In each iteration, we perform training for 100 steps with a batch size of 256 and a learning rate of 2e-5. We adopt a linear warmup for the first 20 steps, followed by a cosine decay to 0. It takes a total of 15 hours on 32 Nvidia H200 GPUs for training and 82 hours on 256 Nvidia H200 GPUs for TES sampling.