LLM 推理中波束搜索的可证明测试时计算扩展

基于集束搜索的测试时间方法通过尽早修剪无效推理路径，提供了一种有效的方法来提高长范围生成上的大语言模型（LLM）性能，从而显着提高推理效率和更有利的测试时间成本缩放。尽管实证上取得了巨大成功，但对集束搜索的理论理解仍然有限。在本文中，我们研究了常用集束搜索框架的测试时计算保证，该框架使用模型的内部对数似然进行中间评分，而仅在生成完整响应后才依赖外部奖励模型。我们首先为普通波束搜索建立一个下限，表明至少需要 $Ω(C^\star(x)^2)$ 样本才能使最佳响应生存，其中 $C^\star(x)$ 是提示 $x$ 的标记级覆盖系数。这激发了我们改进的置信过滤波束搜索（CF-Beam），它在前缀竞争力下将足够的覆盖依赖性从二次减少到接近线性，以实现固定的视野、间隙和目标精度。然后我们证明 CF-Beam 的遗憾是由罕见故障事件的概率和由路径级覆盖系数缩放的奖励估计误差上限决定的，其中罕见故障项随着每步采样的增加而消失。我们的结果强调了波束搜索相对于序列级推理方法（例如“Best-of-N”和“Best-of-Majority”）的基本优势。虽然这些方法的保证通常涉及随着范围 $L$ 呈指数增长的覆盖系数，但 CF-Beam 通过与 $L$ 进行多项式缩放的词元级覆盖系数来控制主要搜索引起的术语。我们的数值实验进一步证实，集束搜索在困难实例和不断增加的推理范围下更加稳健。