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

> Hill Sampling, repeatedly sampling edits to the best program found so far, outperforms all complex evolutionary and weight-space methods, setting new state-of-the-art results on circle packing.

- **Source:** [arXiv](https://arxiv.org/abs/2609.25510)
- **Published:** 2026-09-26
- **Permalink:** https://picx.dev/p/rz03Iv
- **Whiteboard:** https://picx.dev/p/rz03Iv/image

## Summary

## Summary (Overview)

- **Hill Sampling** is introduced as a minimal test-time scaling algorithm: repeatedly sample candidate program edits from a frozen LLM, retain the best program found so far, and condition all subsequent samples on that program.
- **State-of-the-art results**: Hill Sampling sets a new state of the art on circle packing among published methods (score 2.635983084917604, surpassing AlphaEvolve's 2.6358627564136983) in under 5 hours on 8 NVIDIA H100 GPUs, and improves over the AlphaEvolve reference on Erdős' minimum-overlap problem.
- **Key finding on weight-space search**: The largest study by parameter count of evolution strategies (ES) applied directly to LLM weights shows that setting the ES learning rate to zero outperforms actual learning—random weight perturbations help exploration, but token-level sampling randomness is stronger still.
- **Simplicity matters**: A broad evaluation of diversity mechanisms, archives, crossover, entropy control, execution feedback, and multi-step optimization shows all are unnecessary—none improve over Hill Sampling.
- **Practical recommendation**: Before adding elaborate evolutionary harnesses or test-time parameter learning, repeatedly sample edits to the best verified solution found so far.

## Introduction and Theoretical Foundation

The paper addresses a fundamental question in test-time scaling for LLMs: **how much machinery is actually necessary** to obtain strong algorithmic discovery results?

Recent systems like FunSearch (Romera-Paredes et al., 2024), AlphaEvolve (Novikov et al., 2025), and ShinkaEvolve (Lange et al., 2026) use increasingly elaborate evolutionary search harnesses. Other work couples discovery with test-time training (Šurina et al., 2025; Yuksekgonul et al., 2026). The authors ask whether this complexity is needed, starting from the simplest baseline—repeated sampling—and adding only one persistent state: the best verified program found so far.

The theoretical foundation draws on two related lines of work:

1. **Weight-space geometry**: Gan & Isola (2026) argue that useful task-specific experts can be found densely around the weights of sufficiently large pretrained models, motivating random perturbation of model weights and selection/ensembling.

2. **Objective mismatch in RL**: Conventional reinforcement learning optimizes expected reward (pass@1), which can favor safe, homogeneous outputs over the diversity needed for strong pass@k. The discovery objective is the **maximum** observed reward, not the average.

The key insight is that the objective of test-time discovery is:

$$
r^{*} = \max_{i \leq M} r_i \tag{1}
$$

where $M$ is the number of LLM edits. This differs fundamentally from improving average quality—an update can increase expected reward while reducing the probability of a rare, exceptionally good discovery.

## Methodology

### Problem Setting

The authors consider optimization problems with an executable verifier. A state $x$ is a program, executing it produces a scalar reward $r$ (possibly stochastic), and an LLM defines a distribution over edited solutions $y \sim p_{\theta}(\cdot \mid x; T)$ at decoding temperature $T$.

### Hill Sampling Algorithm

Let $x_0$ be the initial program, $x_t$ the current incumbent, and $r_t^{*}$ the best reward observed so far at round $t$. Each round:

1. Draw $N$ edits independently from the current incumbent:
   $$y_{t,1}, \ldots, y_{t,N} \sim p_{\theta}(\cdot | x_t; T) \tag{2}$$
2. Execute each candidate once to obtain rewards $r_{t,1}, \ldots, r_{t,N}$
3. Update the incumbent:
   $$(x_{t+1}, r_{t+1}^{*}) = \begin{cases} (y_{t,i^{*}}, r_{t,i^{*}}) & \text{if } r_{t,i^{*}} \geq r_t^{*}, \\ (x_t, r_t^{*}) & \text{otherwise}. \end{cases} \tag{3}$$
   where $i^{*} = \arg\max_i r_{t,i}$

The incumbent is never re-evaluated; its previously observed reward is retained. New incumbents are accepted with equal reward to promote diversity. **There is no archive, diversity objective, crossover, or parameter update**—the only persistent search state is the incumbent program and its stored best reward.

### Experimental Domains

| Domain | Model | Rounds (N=64) |
|--------|-------|---------------|
| Circle packing (Circles) | gpt-oss-20b | 200 |
| Sums/differences of sets (Sets) | OLMo-3.1-32B-Instruct | 600 |
| Erdős' minimum-overlap (Erdos) | Mistral-Small-3.1-24B-Instruct | 80 |

### Baselines Compared

- **Repeated Sampling (RS)**: Draws candidates from a frozen model without carrying the best program forward.
- **Model Noise (MN)**: Evaluates 64 perturbed models, $\theta_i = \theta + \sigma\epsilon_i$, with antithetic sampling ($\epsilon_{i+32} = -\epsilon_i$).
- **Evolution Strategies (ES)**: Updates the model using the scalable ES estimator (Salimans et al., 2017):
  $$\theta \gets \theta + \frac{\alpha}{32\sigma} \sum_{i=1}^{32} \tilde{R}_i \epsilon_i$$
  where $\alpha$ is the learning rate and $\tilde{R}$ denotes standardized antithetic reward.
- **ES (max@8)**: Evaluates 8 responses per perturbed model, assigning the maximum reward.
- **Hill Sampling + ES**: Combines Hill Sampling with ES updates.

## Empirical Validation / Results

### Main Results (Figure 1)

**Circle Packing**: Hill Sampling is the strongest method, including the no-initial-information (NI) variant, which reaches the same best score as the informed setting. ES performs the worst.

**Sums/Differences of Sets**: No significant difference between methods—all achieve the same top score on some seed, with ES worst on average.

**Erdős' Minimum-Overlap**: Hill Sampling (512) and Hill Sampling (512) + ES perform best. RS achieves high average max return but no single seed matches Hill Sampling. The NI variant is worst, indicating domain knowledge matters here.

### Best-Result Summary (Table 1)

| Domain | Our best | Normalized ↑ | AlphaEvolve | Best prior published | Time | Rounds |
|--------|----------|--------------|-------------|---------------------|------|--------|
| Circles ↑ | 2.635983084917604 | 1.0000456505194 | 2.6358627564136983 | 2.6359830774 (ThetaEvolve) | 4:33 | 14 |
| Sets ↑ | 1.109543 | 0.9578097426685801 | 1.158417281556896 | 1.21 (Hyra) | 1:13 | 2 |
| Erdos ↓ | 0.38089767 | 1.0000665904 | 0.38092303510845016 | 0.380876 (TTT-Discover) | 12:00 | 70 |

### Key Findings on Weight-Space Search

**ES improves mean but not maximum return** (Figure 2): With $\sigma = 10^{-3}$ and temperature 0, a nonzero ES learning rate improves final mean fitness but the best maximum fitness occurs at **learning rate zero**. This demonstrates the objective mismatch: standard ES improves average quality while harming the extreme statistic that matters for discovery.

**Model noise is weaker than ordinary sampling** (Figure 3): Random weight perturbations can provide useful diversity, but ordinary token-sampling randomness from the unperturbed model performs better. On Erdos, temperature-1 Repeated Sampling achieves the best maximum; on Circles, temperature-1 Hill Sampling gives the strongest mean and maximum.

**Entropy interventions don't help** (Figure 4): Adaptive temperature (ATA/ATS) prevents entropy collapse but doesn't improve discovery. Negative-Enhanced Standardization (NE) doesn't even prevent collapse. This is a useful negative control—poor ES maximum isn't explained by entropy collapse alone.

**Broad mechanism comparison on Erdos** (Figure 5): Top-K selection, diverse-K, subpopulation evolution, in-context RL, execution feedback, long-horizon ES, and weight-space hill climbing—**none improve over Hill Sampling**, and most decrease performance.

## Theoretical and Practical Implications

### Theoretical Implications

1. **Objective mismatch is real and consequential**: The paper provides empirical evidence that optimizing for expected reward (as standard ES/RL does) can actively harm the maximum-reward discovery objective. This formalizes a critical distinction between average and extreme statistics in test-time scaling.

2. **Token-level sampling > weight-space perturbations**: In verifiable discovery settings where responses can be evaluated exactly (no generalization needed), the stochasticity inherent in token sampling from a frozen model is more useful than either learned or fixed random weight perturbations. This contextualizes and qualifies the Neural Thickets results of Gan & Isola (2026).

3. **Simplicity as a feature**: The paper challenges the trend toward increasingly complex evolutionary harnesses. The minimal state (best program + best reward) combined with conditioned sampling captures most of the benefit.

### Practical Implications

1. **Default strategy for verifiable domains**: Before adding elaborate machinery, practitioners should try Hill Sampling. The algorithm has only three knobs: temperature, number of rounds, and samples per round.

2. **Compute efficiency**: State-of-the-art results in hours (not days) on 8 H100 GPUs makes this accessible to many research groups.

3. **Domain knowledge caveat**: The paper finds that removing initial domain-specific information doesn't hurt on Circles but substantially hurts on Erdos—practitioners should consider whether domain knowledge is embedded in their initial prompts.

4. **ES learning rate caution**: For those using ES on LLM weights, setting the learning rate to zero (pure noise) can outperform actual learning for discovery objectives.

## Conclusion

The paper introduces **Hill Sampling**, a minimal test-time scaling algorithm that repeatedly samples edits to the best program found so far. Key takeaways:

1. **Hill Sampling sets a new state of the art** on circle packing among published methods and improves over AlphaEvolve on Erdős' minimum-overlap problem, with only hours of computation on eight H100 GPUs.

2. **A learning rate of zero improves ES** via random model perturbations, yet still performs worse than ordinary token sampling.

3. **Further complexity does not help**: Weight-space hill climbing, diversity selection, entropy control, execution feedback, and multi-step optimization all fail to improve performance.

4. **Practical default**: For verifiable domains, repeatedly sample edits to the best solution and let improvements become the next context before adding elaborate evolutionary harnesses or test-time parameter learning.

The paper suggests a clear future direction: understanding *why* Hill Sampling works so well, and identifying the conditions under which additional machinery (archives, diversity mechanisms, test-time training) becomes necessary. The authors also note that domain knowledge can materially affect search, with the effect varying by problem.

---

_Markdown view of https://picx.dev/p/rz03Iv, served by PicX — AI-generated visual whiteboard summaries of research papers._