用最优停止理论优化大模型生成，少跑15%-35%次数仍保持效果。
Optimal Stopping vs Best-of-$N$ for Inference Time Optimization
- 将每次生成视为打开一个代价未知的盒子，动态决定何时停止。
- 实验显示在相同质量下减少15%-35%生成次数，优于固定Best-of-N。
- 适配实际场景，自动归一化奖励并在线学习停止阈值。
大语言模型生成常需权衡输出质量与推理成本，尤其在多次生成时。本文基于经典潘多拉魔盒问题，提出一种推理时优化新框架：将每次生成视为打开一个代价高昂且奖励随机的“盒子”。我们设计了一种类似UCB的潘多拉魔盒算法，其性能可被证明接近已知分布下的最优策略——魏茨曼算法。进一步通过布拉德利-特里变换解决不同提示间的奖励尺度差异，实现自适应推理优化：动态归一化奖励并在线学习停止阈值。在AlpacaFarm与HH-RLHF数据集上，使用多个LLM-奖励模型组合进行实验，结果表明该方法在保持与非自适应Best-of-N相同性能的同时，平均减少15%-35%的生成次数。研究建立了最优停止理论与推理时缩放之间的原则性桥梁，既提供理论性能界，也带来实际效率提升。
原文摘要 · Abstract (English)
Large language model (LLM) generation often requires balancing output quality against inference cost, especially when using multiple generations. We introduce a new framework for inference-time optimization based on the classical Pandora's Box problem. Viewing each generation as opening a costly "box" with random reward, we develop algorithms that decide when to stop generating without knowing the underlying reward distribution. Our first contribution is a UCB-style Pandora's Box algorithm, which achieves performance that is provably close to Weitzman's algorithm, the optimal strategy when the distribution is known. We further adapt this method to practical LLM settings by addressing reward scaling across prompts via a Bradley-Terry inspired transformation. This leads to an adaptive inference-time optimization method that normalizes rewards and learns stopping thresholds on the fly. Experiments on the AlpacaFarm and HH-RLHF datasets, using multiple LLM-reward model pairs, show that our adaptive strategy can obtain the same performance as non-adaptive Best-of-N sampling while requiring 15-35 percent fewer generations on average. Our results establish a principled bridge between optimal stopping theory and inference-time scaling, providing both theoretical performance bounds and practical efficiency gains for LLM deployment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。