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

📄 arXiv: 2609.25510v1 📥 PDF

作者: Jacob Beck, Philip V. Ogren, Ari Kobren

分类: cs.LG, cs.AI

发布日期: 2026-09-22

💡 一句话要点

提出Hill Sampling以优化测试时计算分配策略

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 程序编辑 测试时计算 进化策略 算法优化 圆形打包 Erdos问题 计算效率

📋 核心要点

  1. 现有方法依赖复杂的进化搜索或在测试时更新模型参数，导致计算资源浪费和效率低下。
  2. Hill Sampling通过从固定的LLM中重复采样候选程序编辑，简化了测试时的计算分配策略。
  3. 在多个问题上，Hill Sampling显著提高了性能，尤其是在圆形打包问题上设定了新的状态，计算时间仅需数小时。

📝 摘要（中文）

大型语言模型（LLMs）可以通过在测试时增加计算量来改善可验证的科学和算法问题的解决方案。本文提出了Hill Sampling，一种简单的程序，通过从冻结的LLM中重复采样候选程序编辑，保留迄今为止找到的最佳程序，并将所有后续样本条件化于该程序。我们在圆形打包、集合的和/差以及Erdos的最小重叠问题上评估了该方法，结果显示Hill Sampling在圆形打包问题上设定了新的最优状态，并在Erdos问题上优于AlphaEvolve参考方法。该方法在八个NVIDIA H100 GPU上仅需数小时的计算时间。我们还进行了迄今为止最大规模的进化策略（ES）研究，结果表明，学习权重的效果不如将ES学习率设置为零，后者仍能通过固定随机扰动在权重空间中搜索。随机性来自于令牌采样的效果更强，重复采样的效果显著低于Hill Sampling。

🔬 方法详解

问题定义：本文旨在解决在测试时如何有效利用大型语言模型（LLMs）进行程序编辑的问题。现有方法通常依赖复杂的进化策略或动态更新模型参数，导致计算效率低下和资源浪费。

核心思路：Hill Sampling的核心思想是从一个冻结的LLM中反复采样候选程序编辑，保留当前最佳程序，并将后续的采样条件化于此程序。这种方法避免了复杂的模型更新，简化了计算过程。

技术框架：该方法的整体流程包括：首先从LLM中生成候选程序编辑，然后评估这些编辑的效果，保留最佳的程序，并在此基础上进行后续的采样。整个过程不涉及模型参数的更新，确保了计算的高效性。

关键创新：Hill Sampling的创新在于其简单性和有效性，显著优于传统的重复采样和进化策略。与现有方法相比，它通过固定的随机扰动实现了更有效的探索，避免了复杂的学习过程。

关键设计：在参数设置上，Hill Sampling采用了零学习率的进化策略，确保在权重空间中进行有效的搜索。关键设计还包括对候选程序编辑的评估机制，以确保每次采样都能基于当前最佳解进行优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，Hill Sampling在圆形打包问题上设定了新的状态，超越了现有的所有方法。同时，在Erdos的最小重叠问题上，该方法也优于AlphaEvolve参考，且在有限集合的和/差问题上表现强劲。所有这些结果仅需数小时的计算时间，显示出其高效性。

🎯 应用场景

该研究的潜在应用领域包括科学计算、算法优化和自动程序生成等。Hill Sampling方法的简化计算分配策略能够在多种复杂问题中提供高效的解决方案，具有广泛的实际价值和未来影响。随着LLMs的不断发展，该方法可能会在更多领域得到应用，推动相关技术的进步。

📄 摘要（原文）

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.