Hill Sampling for Test-Time Scaling: A Simple and Better Alternative to Repeated Sampling, Evolution, and Training
在解决该任务旨在为大型语言模型（LLM）分配测试时算力，以有效发现可验证的算法和数学解，并探究复杂的进化机制是否真的必要。
结论它表明使用简单贪心更新的 Token 采样比扰动权重或维护复杂种群提供更强、更廉价的探索，尽管其主打的 SOTA 结果依赖于浮点敏感环境下的单一最佳随机种子，并且在缺乏特定领域提示的情况下表现不佳。
AgentInference
发表 · arXiv 2609.25510
精读于2026-09-23
可信度机制: 高 (算法简单). 涨点: 中 (3个随机种子，存在浮点敏感性). 泛化性: 中 (仅针对标量数学任务).
阅读范围Full LaTeX source, all 2 files incl. appendix given in full; 4 of 15 figures viewed by the reader
精读Gemini 3.1 Pro · 经独立审校
1. 任务
这篇论文致力于解决可验证数学与算法发现（verifiable algorithmic discovery）中的测试时扩展（test-time scaling）问题。给定一个形式化问题（如将圆打包进正方形）和一个能返回标量奖励的可执行评估器，目标是利用 LLM 的推理算力生成并不断改进候选程序，从而发现更优的数学对象。
这个问题的难点在于程序搜索空间巨大，模型很容易陷入局部最优，或者发生模式崩溃（mode-collapse）导致只生成安全但低奖励的代码。此前的方案（如 FunSearch, AlphaEvolve, ShinkaEvolve）通常使用复杂的进化算法——维护种群归档、强制多样性、交叉重组，甚至在测试时更新模型权重（EvoTune, TTT-Discover）。
本文针对一个核心空白：这些复杂的进化和 RL 机制到底有多少是必需的？作者假设，一个极其简单的方案或许就能达到相当甚至更好的发现效果。
2. 核心思路
Hill Sampling（爬山采样）： 抛弃种群、归档和权重更新，直接从冻结的 LLM 中不断采样候选代码，评估后只保留迄今为止找到的唯一最佳程序。所有后续的代码编辑都以此最佳程序为上下文。如果新生成的代码更好，就替换它；否则丢弃。
3. 机制 + 心智模型
机制：
- 初始化起始程序 $x_0$ 并评估其奖励 $r^*_0$。
- 在第 $t = 0 \dots M-1$ 轮：
- 从冻结的 LLM 中，以固定的解码温度（如 $T=1.0$），在当前最佳程序 $x_t$ 的上下文中独立采样 $N$ 个候选编辑（$y_{t,1} \dots y_{t,N}$）。（实验中 $N=64$ 或 $512$）。
- 执行所有候选程序，得到奖励 $r_{t,i}$。
- 找出本轮最高奖励 $r_{t,i^}$ 及对应程序 $y_{t,i^}$。
- 如果 $r_{t,i^} \ge r^t$，则更新当前最佳程序 $x{t+1} = y_{t,i^*}$ 并更新最高奖励。否则保持 $x_{t+1} = x_t$不变。
- 重复直至算力预算耗尽。
心智模型： 在高温度下对冻结模型进行 Token 级别的采样，相比于扰动模型连续参数或进行进化交叉，能提供更丰富、更强力的程序空间探索。将这种强大的探索与贪心的“保留最佳”策略结合，足以驱动优化过程。
4. 指标 / 数据集
- 数据集： 三个可验证的数学优化问题：圆打包（Circles，最大化半径和）、有限集的和与差（Sets，最大化 $C_6$ 下界）、Erdős 最小重叠问题（Erdos，最小化 $C_5$ 上界）。
- 指标： 在固定的 LLM 生成次数预算内发现的最高可验证奖励（图表中相对于 AlphaEvolve 进行了归一化）。
- 模型： gpt-oss-20b (Circles), OLMo-3.1-32B-Instruct (Sets), Mistral-Small-3.1-24B-Instruct (Erdos)。
- 硬件： 8 张 NVIDIA H100 GPU。未报告互联方式。
- 服务栈： vLLM（每张 GPU 一个实例），开启
VLLM_BATCH_INVARIANT并手动为每个响应分配唯一随机种子，以确保不受 batch 影响的严格可复现性。 - Workload： 每轮 64 或 512 次生成；总轮数因任务而异（14 到 600 轮）。评估器初始执行超时设为 5 秒，通过后用 10 秒复测。
5. 对比 baseline
- Baselines： 作者对比了 Repeated Sampling (RS), Model Noise (MN, 固定权重扰动), Evolution Strategies (ES, 学习权重更新) 以及其他 10 多种复杂机制（Top-K, In-Context RL, Execution Feedback）。同时对比了 AlphaEvolve, ThetaEvolve, TTT-Discover 等外部 SOTA。
- 对比是否公平： 作者自己运行的 baseline 对比是完全公平的（模型、框架、硬件、生成预算均一致）。与外部 SOTA 的对比不完全匹配（例如 TTT-Discover 使用了 120B 模型，AlphaEvolve 的底层框架和预算也不同）。
- 核心涨点：
- Circles：Hill Sampling 创下了已发表方法中的新 SOTA 2.6359830849。
- Erdos：达到 0.38089767，超越 AlphaEvolve，但低于 TTT-Discover。
- Sets：达到 1.109543，约为 AlphaEvolve 的 95%（所有 baseline 在此任务上表现相近）。
6. 开源
论文中未提及。（作者称基于开源的 OpenEvolve 框架构建，并记录了超参数，但并未提供自己代码的 URL）。
7. 关键数字核实
| 说法 | 出处 | 实际条件 | 成立? | 备注 |
|---|---|---|---|---|
| 在已发表方法中创下 circle packing 新 SOTA | Tab 1, §1 | 14 轮, gpt-oss-20b, zero-slack 评估器 | ⚠️ | 击败已发表的 ThetaEvolve，但这是 3 个随机种子中的最大值，而非期望回报，并且依赖于对浮点运算顺序极度敏感的无容差 (zero-slack) 评估。 |
| 在 Erdos 问题上超越 AlphaEvolve | Tab 1, §1 | 70 轮, Mistral-24B | ✅ | 仍低于使用了 120B 模型的 TTT-Discover。 |
| 在 Sets 上取得 strong results | Tab 1, Fig 1 | 2 轮, OLMo-32B | ⚠️ | 仅达到 AlphaEvolve 的 95%。所有 baseline 打平，暗示受限于领域知识。 |
| 仅需数小时的 wall-clock time | Tab 1, Abstract | 8x H100s | ✅ | Circles: 4:33, Sets: 1:13, Erdos: 12:00。 |
| 零学习率 (Model Noise) 的最大奖励超越学习后的 ES | Fig 2, §5.1 | Circles, $\sigma=10^{-3}$, $T=0$ | ✅ | ES 更新提高了平均奖励，但主动破坏了最大奖励。 |
| Token 采样优于 Model Noise | Fig 3, §5.1 | Erdos 及其 Circles | ✅ | Temp=1 的 Repeated Sampling 击败了固定权重扰动。 |
| 复杂的多样性/RL 机制没有帮助 | Fig 5, §5.3 | Erdos | ✅ | Top-K、执行反馈和 In-context RL 表现均不如基础的 Hill Sampling。 |
8. 摘要没说的
- 对领域知识的依赖： 移除初始领域代码（“No Initial Information”变体）严重损害了 Erdos 的表现（Fig 1c），尽管令人惊讶的是这对 Circles 没影响。此外，Sets 任务未能击败 SOTA 是因为默认 prompt 限制了搜索空间；当注入领域知识（提示稀疏性）后，成绩逼近 SOTA 的 99%。
- 评估的脆弱性： circle packing 的 SOTA 极其敏感。作者必须在“无容差 (zero-slack)”（不允许重叠）下评估，而在 $10^{-12}$ 的精度下，有效性取决于浮点运算顺序。他们还必须强化评估器以防止 reward hacking。
- 执行超时的影响： 将代码执行超时从 5 秒增加到 20 秒带来了“特别大的改善”，作者指出 wall-clock time 的瓶颈在于 LLM 生成而非执行。
- 熵崩塌不是唯一真凶： ES 模型确实遭遇了熵崩塌（变得过于安全）。然而，通过动态温度缩放人为拉高熵并不能提高发现的最大分数，这证明 ES 本质上与 max@k 目标错配，与崩塌无关。
- 推理 Checklist 发现：
- 指标卫生： 论文严格关注最大回报（类似 pass@k）而非平均回报，准确指出 ES 优化错了目标。
- 加速来源： 通过摒弃交叉、种群和参数更新，Hill Sampling 可以对生成进行大规模 batch 并行，用原始采样吞吐量取代了复杂的状态管理。
9. 可达性与启发
- 可达性： 极高。虽然 8 张 H100 比较昂贵，但算法本身在任何标准 LLM API 或 vLLM 设置上都极易实现，只需要一个 for 循环和基础的字符串拼接。
- 启发 (Inference)：
- 标准的 RL/ES 更新优化的是期望（平均）奖励。如果你只关心单次最优输出（pass@k 或发现任务），这些更新会主动破坏模型发现罕见高回报异常值的能力。
- 在高温度（$T=1.0$）下进行 Token 采样，比对权重连续参数空间进行扰动，是更有效的程序空间探索机制。
- 在构建庞大的多智能体、基于种群的进化框架之前，先写一个简单的贪心“保留最佳”采样循环。它很可能是一个极具竞争力的 baseline。
10. 置信度与下一步
- 机制 (高)： 算法直接，数学上毫无歧义。
- 报告的涨点 (中)： 考虑到方法的极简性，结果令人印象深刻，但每个领域仅测试了 3 个 seed。Sets 领域未能达到 SOTA，且 Circles 严重依赖浮点语义。
- 泛化性 (中)： 仅在具有标量奖励的形式化数学领域进行了测试。尚不清楚在反馈是多维的（如编译错误、测试失败）通用软件工程任务中是否有效。
- 下一步： 鉴于其简单性，非常值得作为任何 Agentic Coding 任务的 baseline 进行复现。建议阅读文中提到的同期工作
gideoni2026simple以了解简单 baseline 在哪些领域会失败。一个未解之谜是：Hill Sampling 能否在不退化为复杂状态机的前提下，融入自然语言的执行反馈？
11. 审校记录
- meta.json task: 将原本陈述论文结论的句子重写为严格的问题定义（为算法发现分配测试时算力）。
- meta.json verdict: 更新以明确指出主要局限性（浮点敏感性、依赖 3 个种子中的最佳值、在没有特定领域提示的情况下表现挣扎），而不仅仅是陈述其贡献和未经验证的领域。
- Section 7 SOTA claim: 将“在 circle packing 上创下新 SOTA”的声明从 ✅ 降级为 ⚠️。主打的数字是 3 个种子中的绝对最大值，而不是期望或中位数回报，并且依赖于极其脆弱的无容差浮点评估顺序。
- 无法验证的事项： 无法验证硬件互联方式或精确的 wall-clock 时间，因为这取决于具体的系统负载。抽查了所有其他数字，发现它们均准确反映了论文的主张和图表内容。