PaperlayerView exact revision on arXiv

Source-linked AI summary

Hill Sampling for Test-Time Scaling: A Simple and Better Alternative to Repeated Sampling, Evolution, and Training

Jacob Beck, Philip V. Ogren, Ari Kobren

arXiv:2609.25510v1cs.LGcs.AI

TL;DR

For verifiable scientific and algorithmic problems, how much elaborate search or test-time training machinery is needed for strong discovery remains an open question. Hill Sampling repeatedly samples edits to the best program found so far; it sets a new state of the art on circle packing and improves on the AlphaEvolve reference on Erdős’ minimum-overlap problem.

  • Problem

    The paper asks how far a simple sampling procedure can go toward strong or state-of-the-art algorithmic discovery under a practical wall-clock budget.

    Source: §1 · p. 2

  • Method

    Hill Sampling repeatedly samples program edits, retains the best-so-far program, and uses each improvement as context for subsequent samples.

    Source: §3.2 · p. 4, §6 · p. 9

  • Results

    Hill Sampling sets a new published state of the art on circle packing, improves on AlphaEvolve for Erdős’ minimum-overlap, and achieves strong results on sums and differences of finite sets.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    For verifiable domains, repeatedly sampling edits to the best solution is a practical default before adding elaborate search machinery or test-time parameter learning.

    Source: §6 · p. 10

    Performance is sensitive to execution timeout, and the experiments use a 5-second default timeout because of experiment volume.

    Source: §4.1 · p. 5

Abstract

from arXiv · show

Large language models (LLMs) can improve solutions to verifiable scientific and algorithmic problems by spending additional computation at test time. Recent systems achieve strong results with increasingly elaborate evolutionary search harnesses or by updating model parameters during test-time training. We ask how much of this machinery is necessary. We introduce Hill Sampling, a simple procedure that repeatedly samples candidate program edits from a frozen LLM, retains the best program found so far, and conditions all subsequent samples on that program. We evaluate the method on circle packing, sums/differences of sets, and Erdos' minimum-overlap problem using three open-weight models. Hill Sampling sets a new state of the art on circle packing among published methods, improves over the AlphaEvolve reference on Erdos' minimum-overlap problem, and achieves strong results on sums and differences of finite sets. The circle-packing and Erdos results require only hours of wall-clock time on eight NVIDIA H100 GPUs. To our knowledge, we also conduct, the largest study, by parameter count, of evolution strategies (ES) applied directly to LLM weights at test time. Surprisingly, learning the weights is worse than setting the ES learning rate to zero: at zero learning rate, the method is still searching in weight space through fixed random perturbations. Those perturbations can help exploration, but randomness from token sampling is stronger still, and repeated sampling remains substantially weaker than Hill Sampling. These results suggest a simple test-time compute allocation strategy: repeatedly sample edits to the best verified solution found so far, before introducing additional complexity such as adding archives, diversity mechanisms, evolutionary scaffolds, or test-time parameter learning.

1 Introduction

The paper introduces Hill Sampling, which conditions repeated samples on the best verified program found so far, and reports strong discovery results with a frozen LLM. It also compares token sampling with evolution strategies and model-weight perturbations for exploration.

1 Introduction

  • At each round, a frozen LLM proposes edits to the incumbent program, and any better verified candidate becomes the best-so-far program conditioning subsequent samples.Hill Sampling adds no archive, crossover, parameter update, or explicit diversity objective.Source: §1 · p. 1
  • Hill Sampling sets a circle-packing state of the art among published methods in under five hours on eight NVIDIA H100 GPUs and improves on the AlphaEvolve reference for Erdős’ minimum-overlap problem in 12 hours.The paper also reports strong results on sums and differences of finite sets.Source: §1 · p. 2
  • The paper reports the largest study by parameter count of evolution strategies applied directly to LLM weights in this setting.Setting the ES learning rate to zero can improve maximum return over training, even with mechanisms intended to prevent entropy collapse.Source: §1 · p. 2
  • ES learning often improves mean return while reducing maximum return; zero-learning-rate perturbations can aid exploration, but token-sampling randomness is stronger and best-program conditioning improves repeated sampling.Hill Sampling outperforms the other methods described in this comparison.Source: §1 · p. 2
  • The authors evaluate mechanisms for diversity, combining solutions, exploration, and using code-execution results, and report that these additions are unnecessary.Their aim is strong or state-of-the-art discovery within a practical wall-clock budget, not the best sample efficiency by evaluations or LLM completions.Source: §1 · pp. 1–2

2 Related Work

Related work spans increasingly elaborate LLM-guided evolution and test-time adaptation, while this paper positions Hill Sampling as a simpler alternative that keeps model weights fixed and changes the program state.

LLM-guided program evolution

  • FunSearch, AlphaEvolve, and ShinkaEvolve use increasingly elaborate LLM-guided evolution, whereas this work prioritizes simple methods with strong discovery performance at reasonable wall-clock cost.FunSearch uses islands, performance-conditioned sampling, and recombination; ShinkaEvolve adds mechanisms including parent selection, novelty rejection, and sub-populations. (Novikov et al., 2025; Lange et al., 2026)Source: §2 · p. 2

Simple discovery baselines

  • Gideoni et al. (2026) found simple sampling methods competitive but not consistently better than AlphaEvolve and ShinkaEvolve; domain-specific prompting mattered on Erdős but not circle packing here.Their simple baselines were worse on all three domains evaluated in this paper; removing the initial domain-specific prompt and code did not affect circle-packing results but reduced Erdős performance.Source: §2 · p. 3
  • Gupta et al. (2026) found no universally best fixed harness and advocated adaptive allocation across harnesses, but did not match or exceed AlphaEvolve; this work's simpler method is competitive.Their study found some components useful and others not consistently beneficial.Source: §2 · p. 3

Test-time training and objective mismatch

  • EvoTune and TTT-Discover train models during discovery, whereas Hill Sampling keeps the model fixed and changes only program state; adding learning was unnecessary in the authors' comparison.EvoTune refines the model with reinforcement-learning updates from evolutionary-search solutions, while TTT-Discover adapts it using experience generated during search. (Šurina et al., 2025; Yuksekgonul et al., 2026)Source: §2 · p. 3
  • PKPO optimizes a joint objective over k responses using a larger batch and subset averaging; the ES max@8 baseline instead takes the maximum of eight responses per perturbed model.The simpler baseline tests whether aligning ES with discovery helps without PKPO's larger-batch estimator, which would reduce the number of independent weight perturbations under a fixed generation budget. (Walder & Karkhanis, 2025)Source: §2 · p. 3

Weight-space search and Neural Thickets

  • ES improved mean return but not maximum performance on 20-billion- to 30-billion-parameter models; zero-learning-rate noise did better, while token sampling and Hill Sampling did better still.The results distinguish learning the weights from searching with fixed perturbations; exact evaluation favors token-level sampling in program space, with Hill Sampling outperforming both learned and fixed random perturbations.Source: §2 · p. 3
  • Neural Thickets motivates random weight-space search around pretrained models, but this paper finds token-level sampling more effective when program responses are exactly verifiable. (Gan & Isola, 2026)Unlike downstream-task evaluation centered on generalization, these experiments use exact evaluation; Hill Sampling outperformed both learned and fixed random weight perturbations.Source: §2 · p. 3

3 Methods

The method targets the best verified reward discovered within a fixed edit budget, rather than average sample quality. Hill Sampling repeatedly samples edits from the current incumbent and uses the best observed reward and program to guide subsequent rounds.

3.1 Problem setting

  • Test-time discovery maximizes the best verified reward found within M LLM edits, a different objective from improving average sample quality.An update can raise expected reward while lowering the chance of a rare, exceptionally good discovery.Source: §3.1 · p. 4

3.2 Hill Sampling

  • Hill Sampling samples N edits from the incumbent each round, executes each candidate once, retains the best observed reward, and lets accepted programs—including equal-reward ones—condition later samples.It has no archive, crossover, diversity objective, or parameter update; its persistent state is the incumbent and its stored best reward.Source: §3.2 · p. 4
  • The N = 64 and N = 512 configurations use the same total sampling budget, trading more frequent incumbent updates for greater parallelizability.Both use eight vLLM instances, one per H100 GPU, with batching-invariant sampling and a unique seed for every response.Source: §3.2 · p. 4

4 Experimental Setup

The experiments evaluate Hill Sampling and test-time-compute baselines across Circles, Sets, and Erdos. The reported comparisons show Hill Sampling leading on Circles and Erdos, while Sets has no significant difference between methods.

4.1 Domains

  • Experiments used three seeds per method and tuned temperatures, arbitrarily assigning one model to each domain and matching compute by LLM completion count.Validation added value and type checks to prevent observed reward hacking.Source: §4.1 · pp. 4–5
  • Increasing execution timeout from 5 to 20 seconds particularly improved performance, but 5 seconds remained the default and passing programs were re-evaluated at 10 seconds.Even at 20 seconds, generation primarily bottlenecked wall-clock time; evaluating each program only once did not significantly affect performance.Source: §4.1 · p. 5
  • Circles maximizes the radii of 26 non-overlapping unit-square circles; Sets optimizes the difference/sumset exponent C6; Erdos minimizes worst-case function/complement overlap, bounding C5.The tasks use gpt-oss-20b for 200 rounds, OLMo-3.1-32B-Instruct for 600 rounds, and Mistral-Small-3.1-24B-Instruct-2503 for 80 rounds, respectively; the Circles and Erdos NI variants omit initial solution context.Source: §4.1 · p. 5

4.2 Baselines

  • Repeated Sampling edits the original code without carrying forward its best program, while Model Noise and Evolution Strategies use antithetic model perturbations, with ES updating model weights.Variants evaluate multiple responses per perturbation, weight perturbations differently, or combine Hill Sampling with ES; Sets comparisons include only batched baselines for computational reasons.Source: §4.2 · p. 5
  • On Circles, only Hill Sampling variants reached top performance and Hill Sampling set a published-method state of the art; on Erdos, Hill Sampling (512) and Hill Sampling (512) + ES performed best and beat AlphaEvolve.On Sets, methods did not differ significantly; all had a seed achieving the same top score.Source: Figure 1 · p. 6, Table 1 · p. 6

5 Results

Hill Sampling leads the reported circle-packing and Erdos comparisons, while added weight-space and entropy-control machinery does not improve the discovery objective. On Sets, all methods perform similarly, and additional prompt domain knowledge improves one separate run.

5 Results

  • Hill Sampling is strongest on circle packing even without initial domain information, matching the informed score, and on Erdos; all methods perform similarly on Sets.On Erdos, removing initial information substantially hurts performance, while adding ES does not improve Hill Sampling.Source: §5 · p. 6
  • In under five hours, Hill Sampling sets a circle-packing state of the art among published methods and beats AlphaEvolve on Erdos, but not the larger gpt-oss-120b result or leading Sets results.The circle-packing comparison is evaluated without slack; the Sets result remains below AlphaEvolve, new autonomous discoveries, and human-assisted constructions.Source: §5 · p. 6

5.1 Model noise: weight-space exploration is not enough

  • On circle packing, nonzero ES learning rates improve final mean return, but maximum return is best at learning rate zero, motivating weight perturbations without updates.Thus, improving average quality can harm the extreme-value discovery objective.Source: Figure 2 · p. 7, §5.1 · p. 7

5 Results

  • A separate gpt-oss-20b run with no initial code and a prompt describing sparse solutions achieves 99.02% of the AlphaEvolve score.The authors suggest the improvement may come from the model and/or domain knowledge; this run is not included in Table 1 because it uses increased domain knowledge.Source: §5 · p. 7, §5.1 · p. 7

5.1 Model noise: weight-space exploration is not enough

  • Fixed Gaussian model perturbations provide diversity but underperform token-sampling randomness: temperature-1 repeated sampling leads Erdos maximum, while temperature-1 Hill Sampling leads circles mean and maximum.For Erdos, greedy decoding (temperature 0) achieves the best final mean among the compared approaches.Source: §5.1 · p. 7, Figure 3 · p. 8

5.2 Entropy collapse: easy to fix, not useful to improve

  • Entropy interventions ATA and ATS prevent entropy collapse but do not significantly improve performance; NE does not prevent collapse, and diversity controls do not recover Hill Sampling’s benefit.This negative control shows that the poor ES maximum is not simply explained by failure to maintain response entropy.Source: Figure 4 · p. 8, §5.2 · p. 9

5.3 Many more methods on Erdos

  • On Erdos, none of the additional tested methods significantly improves Hill Sampling; all except adding ES and ATA to Hill Sampling decrease performance.Erdos was tested most extensively because it requires the fewest improvement rounds.Source: §5.3 · p. 9, Figure 5 · p. 9

6 Conclusion · A Formal Problem Definitions · B Prompts

The paper concludes that repeatedly sampling edits to the best verified solution is a strong default for test-time scaling. Its formal definitions specify the three benchmark objectives, while its prompt appendix distinguishes task-rich standard initialization from no-initial-information settings.

6 Conclusion

  • Hill Sampling sets a published-method state of the art on Circles and improves over the AlphaEvolve reference on Erdos using only hours on eight H100 GPUs.It repeatedly samples edits to the best program found so far.Source: §6 · pp. 9–10
  • Zero-learning-rate ES benefits from random model perturbations but remains weaker than ordinary token sampling, and added search complexity does not improve performance.The conclusion names weight-space hill climbing, diversity selection, entropy control, execution feedback, and multi-step optimization among the additions that did not help.Source: §6 · p. 10

A Formal Problem Definitions

  • For circle packing, the formal task is to maximize the radii of 26 circles in a unit square subject to containment and pairwise non-overlap.The definition specifies centers and nonnegative radii for the circles.Source: A Formal Problem Definitions · p. 12
  • For sums and differences, candidate programs search for a finite set U that maximizes the certified lower bound for C6 under the stated constraint on |U − U|.U is a finite set of non-negative integers containing 0.Source: A Formal Problem Definitions · p. 12
  • For Erdos’ minimum-overlap problem, the upper-bound search optimizes admissible step functions h, with smaller certified overlap giving a stronger upper bound for C5.The formal definition relates C5 to admissible functions f and g and gives an equivalent step-function formulation.Source: A Formal Problem Definitions · p. 12

B Prompts

  • Standard experiments provide task-specific prompts and initial code, whereas no-initial-information experiments retain only the function signature and evaluation code.The no-initial-information comparison tests dependence on domain-specific initialization; the standard circle-packing setup uses phase two of OpenEvolve’s Sharma (2025) prompt schedule.Source: B Prompts · p. 12
  • The prompts set circle packing against AlphaEvolve’s 2.635 target and a 2.377 plateau, while the set and overlap tasks seek improved C6 lower and C5 upper bounds.The C6 prompt cites a current lower bound of 1.158417281556896, and the C5 prompt cites a current upper bound of 0.38092303510845016.Source: B Prompts · pp. 12–13

C Implementation and Hyperparameters · C.1 Hyperparameter Tuning

Hyperparameter tuning selected Model Noise settings and method-specific temperatures under limited compute; on Circles, a faster ES setting increased mean return but reduced max return.

C.1 Hyperparameter Tuning

  • Temperatures were manually tuned over three seeds for each method in each domain in the main results.Model Noise adds entropy beyond temperature, making method-specific temperature tuning useful for adjusting total generation entropy where possible.Source: §C.1 · p. 14
  • Repeated Sampling was tested at temperatures 1.1, 1.0, and 0.5, with 1.0 consistently producing the highest max return.These initial experiments used two seeds on Erdos and Circles to choose tuning ranges, learning rate, and sigma.Source: §C.1 · p. 14
  • Model Noise at temperature 0 performed best with sigma 0.001 on Circles and 0.0006 or 0.0003 on Erdos, but temperature 1.0 improved it in both domains.The initial sigma sweep tested 0.001, 0.0006, 0.0003, and 0.0001.Source: §C.1 · p. 14
  • With sigma 0.0003, learning rate 1e-7 was stable on Erdos and Circles; using sigma 0.0001 and learning rate 1e-6 on Circles improved speed and mean return but decreased max return.The additional setting is consistent with ES optimizing mean return.Source: §C.1 · p. 14
  • In the reported comparison, Model Noise with sigma 0.0003 produced the greatest max returns across two seeds on each domain, so the authors selected it.On Erdos, sigma 0.0003 could be slightly improved by lowering the temperature to 0.95; lowering it further to 0.9 did not improve performance.Source: §C.1 · p. 14
  • Temperatures at or above 1.1 generally caused noticeable declines, so tuning covered [.95, 1.0, 1.05] on Erdos and Circles and [1.0] on Sets.The narrower Sets sweep reflected compute limitations.Source: §C.1 · p. 14

C.2 Other Implementation Details

The implementation fixes shared inference and evaluation settings, then tunes selected evolution-strategy parameters for circle packing and the main experiments.

C.2 Other Implementation Details

  • The implementation uses eight GPU evaluation engines with population size 32, 8,000-token generation, 40,000-token context, and specified sampling and execution-timeout defaults.It uses one vLLM instance per GPU, 32 antithetic samples, top-p 1, antithetic sampling and reward standardization for ES, and temperature 1 for repeated responses unless swept. Default first and second code-execution timeouts are 5 and 10 seconds.Source: §C.2 · p. 15
  • For ES Softmax on circles, beta 2.0 performed best among 0.5, 1.0, and 2.0; main ES experiments use σ = 3 × 10−4 and learning rate 10−7.Circles also tested σ = 10−3 and α = 10−6, which improved mean but not maximum return; earlier experiments used temperature 0.5 and σ = 0.001. Figure 6 is referenced for the results.Source: §C.2 · p. 15

D Evaluator Hardening · E Best Circle-Packing Construction

The appendices describe hardened verifiers that preserve the mathematical objectives while preventing observed reward hacking, and give the program behind the best circle-packing construction.

D Evaluator Hardening

  • The verifiers were hardened to prevent reward hacking observed on Sets while preserving their mathematical objectives, with verifier code visible to the LLM during generation.Source: D Evaluator Hardening · p. 15
  • The circle-packing verifier requires exactly 26 centers and radii and checks that every circle stays within the unit square.Source: D Evaluator Hardening · p. 15
  • The circle-packing verifier also checks every circle pair for overlap, allowing a tolerance of 1e-10.Source: D Evaluator Hardening · p. 15
  • The C6 verifier rejects malformed or invalid sets, including non-integer, too-short, non-finite, duplicate, or negative entries and sets lacking 0.Source: D Evaluator Hardening · pp. 15–16
  • The C6 verifier recomputes the bound from unique pairwise sums and differences and rejects reports that do not match the computed value.Source: D Evaluator Hardening · p. 16
  • The C5 verifier checks the h-values’ shape, [0, 1] range, and integral constraint, then recomputes C5 by correlation and checks the reported value.Source: D Evaluator Hardening · p. 16

E Best Circle-Packing Construction

E.1 Construction · E.2 Program

E.1 presents the best circle-packing construction as a list of center coordinates; E.2 describes a program combining a core-and-shell seed, stochastic refinement, and constrained optimization.

E.1 Construction

  • The best construction is specified by its listed center coordinates.The coordinate list begins in one passage and continues in the next.Source: §E.1 · pp. 16–17

E.2 Program

  • The 26-circle program combines a rounded-hexagon core-and-shell seed, random perturbations, simulated annealing, and SLSQP optimization of radii and centers in log-space.Source: §E.2 · p. 17
  • The program also defines a random-greedy placement routine that falls back to the deterministic initial layout.Source: §E.2 · p. 18
  • During annealing, the program proposes one circle’s radius and center at a time and accepts non-overlapping proposals only when the total radius does not decrease.Source: §E.2 · p. 18
  • The SLSQP objective maximizes the sum of radii subject to square-boundary and pairwise non-overlap constraints.Source: §E.2 · p. 19
  • A shrink step enforces boundary and pairwise feasibility by reducing radii when circles exceed available space.Source: §E.2 · p. 19
  • The program runs 128 initializations, keeps the candidate with the largest radius sum, and applies a packing sanity check before returning it.Source: §E.2 · pp. 19–20

F Additional Method Details

This section specifies how the paper’s alternative sampling, parameter-search, parent-selection, and decoding baselines are implemented. The methods vary whether they propagate programs, update model weights, diversify editing parents, or adapt the decoding context and temperature.

F Additional Method Details

  • Repeated Sampling (RS) edits the original program independently each round, while Model Noise (MN) evaluates perturbed models without accumulating parameter updates.RS starts every round from x0; MN uses 32 antithetic perturbations, with MN (64) drawing one response per perturbed model and MN (512) drawing eight.Source: F Additional Method Details · p. 20
  • Evolution Strategies (ES) updates model parameters using antithetic reward differences, while Hill Sampling + ES combines that update with incumbent-program propagation.ES uses 32 perturbations and their antithetic counterparts; Hill Sampling + ES edits the current best program while updating parameters with the ES procedure.Source: F Additional Method Details · pp. 20–21
  • ES (max@8) uses each perturbation’s best of eight responses as fitness, whereas ES (softmax) replaces standardized reward weights with softmax weights.The max@8 variant shifts the optimization target toward the maximum-over-samples objective used in discovery.Source: F Additional Method Details · p. 20
  • Top-K distributes the highest-reward program states as parents; its variants add random or embedding-dissimilar parents.Top-K + Random-K appends K uniformly sampled prior states, while Top-K + Diverse-K greedily adds states with low average embedding similarity to the selected set.Source: F Additional Method Details · p. 21
  • Top-K In-Context concatenates selected programs into one editing context, while Subpopulation Evolution and In-Context RL maintain separate evolving program histories.Subpopulation Evolution runs 64 subpopulations with eight edits per step for four steps before merging; In-Context RL maintains 512 histories and resets them after four steps.Source: F Additional Method Details · p. 21
  • Execution Feedback conditions later generations on observed execution output, while Auto Temp Add and Auto Temp Scale raise temperature when response entropy falls below its initial mean.Auto Temp Add increments temperature; Auto Temp Scale multiplies it, and both retain increases in subsequent rounds.Source: F Additional Method Details · pp. 21–22
  • Negative-Enhanced Standardization adds a hypothetical maximum reward to normalization statistics, and Long-Horizon ES scores perturbations using the reward after four editing steps.Negative-Enhanced Standardization discards the hypothetical value’s standardized score before the update and is evaluated with and without antithetic sampling.Source: F Additional Method Details · p. 22
  • Weight-Space Hill Climbing adopts the best perturbed model only if its reward exceeds the current model’s, rather than applying a weighted population update.It stores a copy of the prior best weights for exact resetting and repeatable scores.Source: F Additional Method Details · p. 22

Related papers

Loading 2609.25510v1…