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

1. Task

This paper addresses the problem of using test-time scaling for verifiable mathematical and algorithmic discovery. Given a formal problem (like packing circles into a square) and an executable evaluator that returns a scalar reward, the goal is to spend LLM inference compute to generate and improve candidate programs that yield higher rewards (i.e., discover better mathematical objects).

This is challenging because the search space of programs is vast, and models can easily get stuck in local optima or mode-collapse into generating safe, low-reward solutions. Prior approaches like FunSearch, AlphaEvolve, and ShinkaEvolve tackle this using elaborate evolutionary machinery—maintaining archives, enforcing diversity, using crossover, or even training the model weights during test time (EvoTune, TTT-Discover).

The paper targets a fundamental gap: how much of this complex evolutionary and RL machinery is actually necessary? It hypothesizes that a drastically simpler approach might achieve comparable or better discovery results.

2. Core idea

Hill Sampling: Instead of maintaining populations, archives, or updating weights, simply sample candidate edits from a frozen LLM, evaluate them, and keep only the single best program found so far as the context for the next round. If a new edit is better, it becomes the new incumbent; if not, you discard it and try again.

3. Mechanism + mental model

Mechanism:

1. Initialize with a starting program $x_0$ and evaluate its reward $r^*_0$.
2. For round $t = 0 \dots M-1$:
3. Sample $N$ independent candidate edits ($y_{t,1} \dots y_{t,N}$) from the frozen LLM conditioned on the incumbent $x_t$, using a fixed decoding temperature (e.g., $T=1.0$). (The paper uses $N=64$ or $512$).
4. Execute all candidates to obtain rewards $r_{t,i}$.
5. Find the best candidate $y_{t,i^}$ with reward $r_{t,i^}$.
6. If $r_{t,i^} \ge r^t$, set the new incumbent $x{t+1} = y_{t,i^*}$ and update the max reward. Otherwise, keep $x_{t+1} = x_t$.
7. Repeat until the budget is exhausted.

Mental model: Token-level sampling from a frozen model at high temperature provides a richer and stronger form of exploration in program space than either perturbing continuous model weights or doing evolutionary crossover, and coupling this with a greedy "keep the best" selection is enough to drive optimization.

4. Metrics / data

• Benchmarks: Three verifiable mathematical optimization problems: Circle packing (Circles, max sum of radii), Sums and differences of finite sets (Sets, max $C_6$ bound), and Erdős' minimum-overlap problem (Erdos, min $C_5$ overlap bound).
• Metrics: Maximum verified reward found within a fixed budget of LLM completions (reported as absolute numbers and normalized against AlphaEvolve).
• Models: gpt-oss-20b (Circles), OLMo-3.1-32B-Instruct (Sets), Mistral-Small-3.1-24B-Instruct (Erdos).
• Hardware: 8 NVIDIA H100 GPUs. Interconnect not reported.
• Serving stack: vLLM with VLLM_BATCH_INVARIANT enabled and manually assigned unique seeds per response to ensure strict reproducibility regardless of batching.
• Workload: 64 or 512 completions per round; total rounds vary by task (14 to 600). The evaluator uses a 5-second initial execution timeout, with a 10-second re-evaluation for passing code.

5. vs. baseline

• Baselines: The authors compare against Repeated Sampling (RS), Model Noise (MN, fixed weight perturbations), Evolution Strategies (ES, learned weight updates), and 10+ other complex mechanisms (Top-K, In-Context RL, Execution Feedback). They also compare against external SOTAs like AlphaEvolve, ThetaEvolve, and TTT-Discover.
• Fairness: Internal baseline comparisons are perfectly matched (same model, harness, hardware, and completion budget). External comparisons are not matched (e.g., TTT-Discover used a 120B model; AlphaEvolve used a different LLM and budget).
• Headline gains:
  • Circles: Hill Sampling sets a new published SOTA of 2.6359830849.
  • Erdos: Achieves 0.38089767, beating AlphaEvolve but remaining behind TTT-Discover.
  • Sets: Achieves 1.109543, which is ~95% of AlphaEvolve (all baselines tied here).

6. Open source

Not mentioned in the paper. (The authors state they built on the open-source OpenEvolve framework and documented hyperparameters, but do not provide a URL to their own code).

7. Key numbers, verified

8. What the abstract doesn't say

• Domain knowledge reliance: Removing the initial domain-specific code ("No Initial Information" variant) severely hurt performance on Erdos (Fig 1c), though surprisingly it didn't hurt Circles. Furthermore, the Sets task failed to beat SOTA because the default prompt restricted the search space; injecting domain knowledge (hinting at sparsity) brought it to 99% of SOTA.
• Evaluation fragility: The circle packing SOTA is highly sensitive. The authors had to evaluate without "slack" (zero overlap allowed), and at this level of precision ($10^{-12}$), validity depends on floating-point operation order. They also had to harden the verifiers to prevent reward hacking.
• Execution timeouts matter: Increasing the code-execution timeout from 5s to 20s provided a "particularly large improvement", noting that wall-clock time is bottlenecked by LLM generation, not execution.
• Entropy collapse isn't the only culprit: ES models suffered from entropy collapse (becoming too safe). However, artificially forcing entropy up (via dynamic temperature scaling) didn't improve discovery max scores, proving ES fundamentally misaligns with the max@k objective, independent of collapse.
• Inference checklist:
  • Metric hygiene: Focuses strictly on maximum return (pass@k analog) rather than mean return, correctly identifying that ES optimizes the wrong thing.
  • Where the speedup comes from: By discarding crossover, populations, and parameter updates, Hill Sampling can heavily batch parallel generations, trading complex state management for raw sampling throughput.

9. Reachability + takeaways

• Reachability: Extremely high. While 8x H100s is somewhat expensive, the algorithm itself is trivial to implement over any standard LLM API or vLLM setup. It requires only a loop and basic string manipulation.
• Takeaways (Inference):
  • Standard RL/ES updates optimize for expected (mean) reward. If you only care about the single best output (pass@k, discovery), these updates can actively destroy the model's ability to find rare, high-reward outliers.
  • Token sampling at a high temperature ($T=1.0$) is a much more effective exploration mechanism for program space than perturbing the continuous parameter space of the weights.
  • Before building a massive multi-agent, population-based evolutionary harness, set up a simple greedy "keep-the-best" sampling loop. It is likely a highly competitive baseline.

10. Confidence + next steps

• Mechanism (High): The algorithm is straightforward and mathematically unambiguous.
• Reported gains (Medium): The results are impressive given the simplicity, but rely on only 3 seeds per domain. The Sets domain failed to match SOTA, and Circles is heavily tied to floating-point semantics.
• Generality (Medium): Tested purely on formal mathematical domains with scalar rewards. It is unclear if this holds for general software engineering where feedback is multi-dimensional (e.g., compiler errors, test failures).
• Next steps: This is worth reproducing as a baseline for any agentic coding task. Read the concurrent gideoni2026simple paper mentioned in the text to see where simple baselines fail. An open question is whether Hill Sampling can incorporate natural language execution feedback without degrading into a complex state machine.

11. Audit

• meta.json task: Rewrote from a conclusion (stating the paper's findings) to a strict problem statement (allocating test-time compute for algorithmic discovery).
• meta.json verdict: Updated to explicitly mention the main limitations (float-sensitivity, relying on best-of-3 seeds, struggling without domain-specific prompts) rather than just stating the contribution and an untested domain.
• Section 7 SOTA claim: Downgraded the "Sets new SOTA on circle packing" claim from ✅ to ⚠️. The headline number is the absolute maximum over 3 seeds, not the expected or median return, and relies on a highly fragile zero-slack floating-point evaluation order.
• Unverifiable: Could not verify the hardware interconnect or precise wall-clock reproduction, as it depends on exact system loads. Spot-checked all other numbers and found them to accurately reflect the paper's claims and figures.