Hill sampling improves test time problem solving with large language models
Hill Sampling for Test-Time Scaling: A Simple and Better Alternative to Repeated Sampling, Evolution, and Training
Machine LearningArtificial Intelligence
Summary
Solving difficult problems with large language models often uses complicated tricks to get better answers during testing. The authors show that a much simpler method called Hill Sampling, which keeps and improves the best solution found so far by repeatedly editing it, works better than these complex methods. They tested it on several mathematical problems and it gave better or comparable results with less time and complexity. Surprisingly, trying to change model weights at test time didn’t help as much as just sampling many edits from the model.
What this means in practice
- •For software developers: Improve algorithmic problem-solving tools that use LLMs by implementing simple repeated edit sampling instead of complex test-time training or evolutionary methods.
- •For optimization engineers: Accelerate solutions to verified scientific problems like packing and set arithmetic using straightforward test-time search with frozen language models.
Authors
Jacob Beck, Philip V. Ogren, Ari Kobren
Abstract
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.