Hill Sampling for Test-Time Scaling: A Simple and Better Alternative to Repeated Sampling, Evolution, and Training
Jacob Beck, Philip V. Ogren, Ari Kobren
cs.LG · cs.AI
Quick verdict
Claims simple best-so-far sampling beats evolution/training for LLM discovery; convincing qualitatively, but SOTA margins sit at float-precision limits.
Summary
The paper introduces Hill Sampling, a minimal test-time scaling procedure in which a frozen LLM repeatedly proposes edits to the best verified program found so far; a candidate replaces the incumbent only when its verified reward matches or exceeds it. Using three open-weight models (gpt-oss-20b, OLMo-3.1-32B-Instruct, Mistral-Small-3.1-24B-Instruct) on circle packing (26 circles), sums/differences of finite sets (C6), and Erdős' minimum-overlap problem (C5), with compute matched by LLM completions, the authors report a new state of the art on circle packing (2.6359830849, marginally above ThetaEvolve) in under five hours on eight H100s, and 0.38089767 on Erdős, beating AlphaEvolve's 0.38092303 but not TTT-Discover's 0.380876; on sets the result reaches only ~95.8% of AlphaEvolve's score. They also run the largest evolution-strategies study by parameter count on LLM weights, finding learning improves mean return but degrades maximum return, weight perturbations lose to token-sampling randomness, and archives, diversity mechanisms, entropy control, and execution feedback add nothing. Limitations: three seeds per configuration with no significance tests, one model per domain, headline margins at floating-point precision, and best results obtained under longer evaluation timeouts than the experimental default.
Review complete
Assessment at a glance
0
risk flags identified
● high 0
● medium 0
● low 0
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Repeatedly sampling edits to the best verified program (Hill Sampling) is a stronger test-time allocation than repeated sampling, evolutionary scaffolds, or test-time weight training on three verifiable math domains.
- Hill Sampling sets a new state of the art among published methods on 26-circle packing (2.6359830849) in under five hours on eight H100s, and improves on the AlphaEvolve reference on Erdős' minimum-overlap (0.38089767 vs 0.38092303).
- At the largest scale to date (20B-30B parameters), ES weight learning improves mean return but reduces maximum return; setting the learning rate to zero (fixed random weight perturbations) is better than learning but still worse than token-sampling randomness.
- A broad battery of added mechanisms — archives, Top-K and diversity parents, in-context RL, execution feedback, entropy interventions, weight-space hill climbing — provides no significant advantage over plain Hill Sampling.
Strengths
Radically simple, precisely specified method
The procedure is fully specified in §3.2 (Eqs. 2–3) with only three knobs (temperature, rounds, samples per round); Appendix C documents vLLM batch-invariance settings and per-response seeds, enabling faithful reimplementation.
Honest negative results at unprecedented ES scale
The ES study shows mean-vs-max objective mismatch (Fig. 2: nonzero learning rate improves final mean fitness but maximum fitness peaks at learning rate zero), and §5.2's entropy interventions serve as a negative control showing the poor ES max is not explained by entropy collapse.
Unusually transparent reporting of concurrency and failure
High reproducibility documentation
Breadth of falsification effort
Weaknesses
Headline SOTA margin sits at floating-point resolution under a self-authored verifier
No formal statistical inference anywhere
One model per domain, and per-domain baseline sets
Evaluation-budget asymmetry between headline and experimental numbers
Erdős improvement is thin and third place overall
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper asks how much machinery LLM-based program discovery actually needs. Its proposed answer, Hill Sampling (HS, §3.2), keeps exactly one persistent state — the best verified program — and conditions all sampled edits on it, accepting ties (Eq. 3). Claims: (1) new SOTA among *published* methods on 26-circle packing, (2) improvement over the AlphaEvolve reference on Erdős' minimum-overlap, (3) strong-but-below-SOTA results on sums/differences of sets, (4) at 20B–30B parameter scale, ES weight learning hurts the max objective relative to zero learning rate, and (5) none of the surveyed added mechanisms helps. The scope is deliberately one of wall-clock practicality, not sample efficiency — a fair framing.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 0 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Hill Sampling in simple terms?
It is a minimal test-time search loop: a frozen LLM repeatedly proposes edits to the current best verified program, each candidate is scored once by an executable verifier, and the incumbent is replaced only when a candidate scores at least as well (ties included). There is no archive, crossover, diversity objective, or parameter update — the only state is the incumbent program and its reward.
Does Hill Sampling beat AlphaEvolve?
Partly. On Erdős' minimum-overlap problem it improves on the AlphaEvolve reference (0.38089767 vs 0.38092303, lower is better) but does not beat the best published number (TTT-Discover, 0.380876). On circle packing (26 circles) it reports a new record among published methods (2.6359830849 vs ThetaEvolve's 2.6359830774), by a razor-thin floating-point margin. On sums/differences of sets it reaches only about 95.8% of AlphaEvolve's score.
How much compute does Hill Sampling need?
The headline results used eight NVIDIA H100 GPUs: under five hours for the circle-packing record and 12 hours for the Erdős result. Compute across compared methods was matched by the number of LLM completions (best results were found at round 14 and round 70 respectively, with 512 completions per round).
Is code available for this paper?
The method itself is simple enough to reimplement, and the paper builds on the open-source OpenEvolve harness, documenting prompts (Appendix B), hardened verifiers (Appendix D), hyperparameters (Appendix C), and the full best construction (Appendix E). However, the text states no explicit code release; the record margins also depend on floating-point evaluation details, so exact re-derivation requires care.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Abstract truncated mid-sentence in extraction; full abstract claims taken from body text
- All figures (1-6) available only via captions; underlying curves and exact effect sizes not analyzable
- Numerous cited works are 2025-2026 preprints/concurrent results that cannot be cross-checked from the text
- Mathematical notation passed through OCR; minor symbol corruption possible in equations and appendix code
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.