- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces Hill Sampling (HS), which uses a frozen LLM to sample batches of edits to the best verified program found so far. The best candidate replaces the incumbent if its reward is at least as high, and becomes the context for the next round. The authors evaluate HS on circle packing, sums and differences of finite sets, and Erdős' minimum-overlap problem against additional search mechanisms (RS, Model Noise, ES). HS achieves competitive results. The main contributions are a simple search baseline and an empirical analysis of mean return versus maximum return.
Critical strengths
-
The simple search baseline has practical value. HS achieves strong mathematical search results without parameter updates or an elaborate program database. These results offer a useful baseline for assessing the benefits of more complex discovery systems.
-
The distinction between mean return and maximum return is informative. Experiments with ES, max@8, Model Noise, and entropy control show that improving average quality need not improve the best solution found. These controls help characterize the limitations of test-time learning for discovery.
Critical weaknesses
-
This paper provides new empirical results on mathematical discovery, but its methodological contribution needs clearer positioning.** Algorithm 1 in the (1+1)-EPS paper (arXiv 2407.10873) already uses a closely related search loop, and the study reports competitive performance. ShinkaEvolve (arXiv 2509.19349) also evaluates selecting the best program as the parent on circle packing. Relative to EPS, the main differences are batched sampling and accepting equal-reward candidates. The paper compares N = 64 and 512 but does not report N = 1, where each candidate is evaluated and the incumbent can be updated before the next candidate is generated. If batching is the main methodological addition, a comparison under otherwise matched settings and total LLM completions, with wall-clock time reported separately, would help isolate its benefits for search quality and efficiency.
-
The HS and RS comparisons support propagating the best program in some settings, but do not fully establish the recommendation to allocate search compute to HS first. The authors describe some initialization sources and include NI ablations. However, they do not consistently report initial verified scores or best-so-far score trajectories for HS and the baselines. The iterative improvement over initialization and the cost of progress at different search stages therefore remain unclear.
-
Results across seeds show that pure HS is competitive, but the abstract's claim that “HS is the strongest of all” is broader than the detailed findings. The paper defines the objective as the maximum observed verified reward within a fixed generation budget. However, the Figure 1 caption reports no significant difference between methods on Sets and identifies both HS and HS + ES as the best methods on Erdős. The broader mechanism comparison in Figure 5 is also limited to Erdős with Mistral. A lack of observed gains in this setting does not establish that these mechanisms are generally unnecessary.
-
Comparisons within each domain use the same base model, but robustness across models remains unclear. The main experiments use gpt-oss-20b for Circles, OLMo for Sets, and Mistral for Erdős, leaving model and domain effects intertwined across tasks. The additional runs with different models do not systematically repeat the method comparisons, and the Sets run also changes the prompt and execution settings. These limitations weaken the support for the broader conclusions.
Questions for authors
Could the author clarify the contribution beyond prior best-program search methods and the scope of the claims discussed in the weaknesses above? Are there existing N = 1 results, search trajectories, or comparisons across models that further support these claims and the recommendation to use HS first?
2 comments
Questions For Authors: “Could the author clarify the contribution beyond prior best-program search methods… and the recommendation to use HS first?” Hill Sampling can be seen as a simplification of many existing algorithms, including (1+1)-EPS. (See 1. for details.) However, we still provide much more convincing scale, simplification, and empirical results, relative to prior work. A central contribution of this paper is demonstrating that this simple algorithm can achieve state-of-the-art results among published methods when scaled appropriately, which, to our knowledge, has not previously been demonstrated at this level of performance. In response to comments, we have also generated additional plots (See 2. for details) to support our claims to use HS first. We have additionally added text to resolve ambiguity in claims (3.), noting that HS performs better than, or not significantly different from, all methods evaluated, and that HS is better, overall, compared to all existing baselines measured. Overall, we believe we clearly show that an extremely simple search principle can reach state-of-the-art mathematical discovery results, while the ES experiments also reveal important limitations of parameter-space optimization for best-solution discovery, which collectively more than justify the contributions of this paper.
Thank you for your feedback and for noting the practical value of Hill Sampling and the value of the ES results. In response to these comments, we have added text and additional plots to our results. If you agree with the responses, please do increase our score, and if not, please let us know where we still disagree: