Provable Test-Time Scaling for Beam Search in LLM Reasoning¶
会议: NeurIPS 2026
arXiv: 2609.38672
领域: 其他
关键词: 束搜索 / 测试时缩放 / 大语言模型推理 / 置信度过滤 / 遗憾界分析
一句话总结¶
针对大语言模型长链推理中序列级采样方法测试时计算预算随长度指数爆炸的问题,本文首次建立了束搜索的测试时计算理论保证,揭示了朴素束搜索面临的二次方覆盖度样本下界,并提出了置信度过滤束搜索(CF-Beam),证明其将搜索失误导致的样本复杂度从二次方优化为近线性依赖,且主导项随推理步长仅多项式增长。
研究背景与动机¶
在复杂数学推理、算法规划和多步逻辑推导等长链生成任务中,大语言模型仅依赖单次自回归贪婪解码极易因中间步骤微小的误差累积导致最终推理崩溃。为了打破模型参数规模的固化约束,测试时计算(Test-Time Compute)逐渐成为提升推理能力的关键范式。主流的序列级并行采样方法,例如 Best-of-N(BoN)采样和多数投票法(Majority Voting)及其衍生策略(如 Best-of-Majority),通过在生成完整序列后进行过滤与加权来选优。然而,这类方法在稀疏成功与长推理路径场景下暴露出严重的扩展瓶颈:随着生成上下文长度的增长,为了维持输出正确率,所需采样的序列总数必须随序列级覆盖系数呈指数级攀升;同时,若最终检验器(Reward Model / Verifier)存在分布估计误差,序列级方法更容易陷入虚假候选与错误过拟合。
相比于在完整响应生成后进行事后筛选的序列级方法,束搜索(Beam Search)作为经典的分步剪枝策略,通过在每个中间生成步骤维护前 \(b\) 个最具潜力的前缀并剪裁劣质分支,展现出了极高的探索效率与更优的经验缩放行为。然而,尽管束搜索在经验上被广泛应用于大模型推理加速,学术界对其在有限样本采样与不完美验证器设定下的理论缩放保证仍缺乏系统研究。这主要受制于逐步剪枝在自回归演化过程中引入的强时序依赖性,以及启发式中间打分指标与全局真实目标之间的不对齐。现存的关键理论问题在于:在仅具备黑盒采样访问权限且仅在完整序列末尾获得稀疏外部奖励的实际场景中,束搜索究竟遵循怎样的测试时计算缩放律?相较于传统的序列级推断机制,束搜索是否具有严格可证的样本复杂度与遗憾界优势?
核心 idea:通过在每个生成步骤引入基于经验采样频率的局部置信度阈值过滤,构造置信度过滤束搜索(CF-Beam),彻底滤除低概率长尾动作对最优前缀的竞争挤压,从而在理论上将保证最优路径存活所需的每步采样复杂度从二次方覆盖系数 \(\Omega(C^\star(x)^2)\) 压缩至近线性 \(\widetilde{O}(C_{\max}^\star)\),并将搜索诱导的计算预算从随生成步长指数增长转变为多项式增长。
方法详解¶
整体框架¶
CF-Beam 旨在解决黑盒参考策略 \(\pi_{\text{ref}}\) 下,仅能通过蒙特卡洛多步采样估计局部转移概率且仅在最终步提供标量奖励模型 \(\hat{r}(x,y)\) 时的测试时最优解码问题。整个推断流程包括四个核心阶段:前缀扩展采样、经验概率估计与置信度过滤、累计对数似然累加与 Top-\(b\) 束更新、以及最终的奖励打分(或自洽对数似然选择)。算法输入初始前缀集合 \(\mathcal{B}_0 = \{\emptyset\}\),在每个推断步 \(t=1,\dots,L\),对当前束内保留的每个前缀独立进行 \(N\) 次局部单步采样;计算每个生成动作的经验频率后,直接剔除低于阈值 \(\beta_t\) 的候选动作;将存活前缀的累计经验对数似然更新并排序,截取前 \(b\) 个前缀进入下一轮;最终在达到长度 \(L\) 的候选集合 \(\mathcal{B}_L\) 中,调用外部奖励模型选取分值最高的完整序列 \(\hat{y}\)。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入 Prompt x 与初始束 B_0"] --> B["前缀扩展采样<br/>对每个存活前缀采样 N 次"]
B --> C["经验对数似然打分与有限样本失效机制<br/>计算动作经验频率与路径分数"]
C --> D["基于置信度过滤的束搜索<br/>根据阈值 beta_t 过滤低频长尾动作"]
D --> E["Top-b 剪枝保留前 b 个最佳前缀<br/>更新生成深度 t 至 L"]
E --> F["双重解耦的遗憾界与无奖励模型扩展<br/>调用奖励模型或最终经验分数选优"]
F --> G["输出最终最优推理轨迹 y_hat"]
关键设计¶
1. 经验对数似然打分与有限样本失效机制:揭示低概率长尾扰动的脆弱性 在无法直接访问底层模型完整 Logits 的黑盒采样设定下,标准束搜索(Vanilla-Beam)必须完全依赖有限样本的经验频数 \(\hat{\pi}(a_t \mid s_{t-1}, x) = \frac{1}{N} \sum_{i=1}^N \mathbf{1}(a_t^{(i)} = a_t)\) 构建内部对数似然评分 \(Q(s_t) = \sum_{i=1}^t \log \hat{\pi}(a_i \mid s_{i-1}, x)\)。然而,大语言模型的词表空间通常极其庞大(例如 \(|\mathcal{A}| \geq 10^4\)),绝大多数语义无关或低质量的词元处于分布的长尾区。虽然这些词元真实采样概率极低,但由于采样总预算有限,在单次实验中偶尔出现的偶然命中会被有限样本频率严重高估。当执行严格的 Top-\(b\) 硬性截断时,这些被偶然放大的长尾候选路径会迅速抢占有限的束容量,导致真实的最优前缀 \(s_t^\star\) 被不可逆地剔除。本文在定理 1 中给出了严格的失败下界证明:存在满足常数覆盖度 \(C^\star(x)\) 的良态实例,若每步采样量 \(N \leq (C^\star(x))^2 / 16\),朴素束搜索以至少 0.5 的恒定概率在推断过程中彻底丢弃最优轨迹。这意味着标准束搜索必须支付至少 \(\Omega(C^\star(x)^2)\) 的二次方采样代价才能保证正确答案存活。
2. 基于置信度过滤的束搜索(CF-Beam):将覆盖度依赖从二次方压缩至近线性 为了克服有限样本长尾噪声挤出最优路径的瓶颈,CF-Beam 在经验概率计算后、路径合并截断前引入了显式的置信度阈值过滤准则。具体而言,对任意在采样中出现至少一次的候选动作 \(a_t\),只有当其经验采样概率满足 \(\hat{\pi}(a_t \mid s_{t-1}, x) \geq \beta_t\) 时才被允许生成扩展候选分支 \(s_t' = s_{t-1} \oplus a_t\),否则直接舍弃。在理论分析中,选择理论预言机阈值 \(\beta_t = (1 - 1/L) / C_t^\star(x)\)(其中 \(C_t^\star(x) = 1/\pi_{\text{ref}}(a_t^\star \mid s_{t-1}^\star, x)\) 为最优动作的逆概率);而在实际落地中,本文设计了自适应前缀的经验阈值 \(\beta_t(s_{t-1}) = \gamma \max_{a \in \mathcal{A}} \hat{\pi}(a \mid s_{t-1}, x)\)(其中 \(\gamma \in (0, 1)\),实验取 0.3)。置信度过滤的核心机理在于:由于最优前缀满足前缀竞争性假设(Prefix Competitiveness,即在相同前缀下最优动作与次优动作保持可分边际 \(\kappa\)),通过 Chernoff 下尾不等式,最优动作低于阈值的过滤失误概率以指数速率衰减;同时,该过滤条件从根本上截断了总概率质量极小但因离散抽样出现的高方差扰动,使得任何单个次优前缀能够凭借偶然波动战胜最优前缀的概率被严格压制。定理 2 表明,CF-Beam 将保证最优路径存活所需的单步采样量从 \(O((C_{\max}^\star)^2)\) 骤降至 \(\widetilde{O}(C_{\max}^\star)\),实现了覆盖度依赖的近线性化。
3. 双重解耦的遗憾界与无奖励模型扩展:兼顾奖励估计误差与多项式步长缩放 CF-Beam 的性能表现由搜索误差(Search Error)与验证器误差(Reward-Model Error)联合决定。定理 2 建立了 CF-Beam 在真实奖励下的预期遗憾上界: $\(\mathrm{Reg}(x) \leq L\exp\left(-\frac{N}{2C_{\max}^{\star}L^{2}}\right) + \frac{2C_{\max}^{\star}}{b}\exp\left(-\frac{\kappa^{2}N}{48C_{\max}^{\star}}\right) + \epsilon_{\mathrm{opt}}(x) + 2\sqrt{\overline{C}(x)\epsilon_{\mathrm{RM}}^{2}(x)}\)$ 其中前两项构成了搜索失误概率 \(\mathbb{P}(\mathcal{E}^c)\),分别对应过滤阶段错杀最优动作与剪枝阶段最优动作被竞争者挤出前 \(b\) 名的失误界。这一界展现出深远的技术优势:与序列级推理方法(如 Best-of-N 和 Best-of-Majority)中搜索复杂度严重依赖轨迹联合覆盖度 \(\overline{C}(x) = \prod_{t=1}^L C_t^\star(x)\)(随生成长度 \(L\) 呈指数爆炸)不同,CF-Beam 的搜索失误项仅依赖局部单步最大覆盖系数 \(C_{\max}^\star = \max_t C_t^\star\),对长度 \(L\) 的依赖严格被限制在多项式级别(总查询预算为 \(\widetilde{O}(b L^3 C_{\max}^\star)\))。进一步地,针对现实中外部奖励模型不可用或标注噪声极大的难题,本文提出了完全自洽的无奖励模型变体(Algorithm 2):直接在最终保留的束 \(\mathcal{B}_L\) 中依据累积自洽对数似然 \(Q_L(y)\) 选取最终输出。推论 2 证明,该无奖励模型版本的遗憾界完全摆脱了验证器误差项,总查询预算仅需随生成步长 \(L\) 呈近线性增长 \(\widetilde{O}(L b C_{\max}^\star / \kappa^2)\)。
损失函数 / 训练策略¶
作为推断阶段的测试时缩放算法,CF-Beam 无需对模型参数进行任何反向传播或梯度更新,基座模型权重在整个推断过程中保持冻结。算法的核心计算策略集中在测试时查询预算的分步动态分配与离散决策: 1. 单步打分准则:在扩展阶段,候选动作的评分累加采用经验对数似然: $\(Q(s_t) = Q(s_{t-1}) + \log \hat{\pi}(a_t \mid s_{t-1}, x) = \sum_{i=1}^t \log \left( \frac{1}{N} \sum_{j=1}^N \mathbf{1}(a_i^{(j)} = a_i) \right)\)$ 2. 过滤与剪枝操作:定义中间状态转移候选集合为 \(\mathcal{D}_t = \{s_{t-1} \oplus a_t \mid s_{t-1} \in \mathcal{B}_{t-1}, \hat{\pi}(a_t \mid s_{t-1}, x) \geq \beta_t\}\),随后更新束为 \(\mathcal{B}_t = \text{top-}b \{s_t' \in \mathcal{D}_t \text{ ranked by } Q(s_t')\}\)。 3. 最终决策规则:在标准设定下,利用预训练结果验证器计算 \(\hat{y} = \arg\max_{y \in \mathcal{B}_L} \hat{r}(x, y)\);在无验证器自洽设定下,计算 \(\hat{y} = \arg\max_{y \in \mathcal{B}_L} Q_L(y)\)。 4. 总计算开销核算:算法的总策略查询预算被严格界定为 \(B(x) \leq L \cdot b \cdot N\)。在给定的推断延迟约束下,可以通过调节束宽 \(b\) 与单步采样量 \(N\) 实现计算资源在宽度探索与深度精度之间的最优配置。
实验关键数据¶
主实验¶
为了验证理论发现,作者在真实大模型评测中采用了 Qwen3-1.7B-Base 模型,在 500 个合成 4×4 整数矩阵乘法多步推理问题上进行评测。模型采样温度设置为 1.3,生成的最终完整序列由专用数学验证器 AceMath-7B-RM 进行质量评估。束搜索方法固定单步采样量 \(N=12\) 与束宽 \(b=2\),CF-Beam 采用经验置信度过滤参数 \(\gamma=0.3\)。
| 方法 (Method) | 采样模式 | 准确率 (Accuracy) | 策略查询预算 (Budget, \(\times 10^3\)) | 相比 Best-of-N 提升 |
|---|---|---|---|---|
| Best-of-N | 序列级独立采样 | 0.332 | 16.8 | 基准 (0.0%) |
| Majority Voting | 序列级频数投票 | 0.304 | 16.8 | -2.8% |
| Best-of-Majority | 序列自洽过滤+打分 | 0.326 | 16.8 | -0.6% |
| Vanilla-Beam | 分步朴素束搜索 | 0.372 | 18.6 | +4.0% |
| CF-Beam (Empirical) | 分步置信度过滤束搜索 | 0.388 | 16.2 | +5.6% |
消融实验¶
在相同的 Qwen3-1.7B-Base 矩阵乘法任务上,作者系统消融了置信度过滤阈值比例系数 \(\gamma \in \{0, 0.15, 0.3, 0.45, 0.6, 0.75, 0.9\}\) 以及束宽 \(b \in \{2, 4, 8\}\) 对推理准确率的影响(其中 \(\gamma=0\) 即退化为未做置信度过滤的 Vanilla-Beam)。
| 束宽 (\(b\)) | \(\gamma=0\) (Vanilla) | \(\gamma=0.15\) | \(\gamma=0.3\) | \(\gamma=0.45\) | \(\gamma=0.6\) | \(\gamma=0.75\) | \(\gamma=0.9\) | 说明 |
|---|---|---|---|---|---|---|---|---|
| \(b=2\) | 0.372 | 0.378 | 0.388 | 0.372 | 0.318 | 0.292 | 0.290 | 中等过滤系数 \(\gamma=0.3\) 取得最佳性能 |
| \(b=4\) | 0.482 | 0.512 | 0.472 | 0.392 | 0.374 | 0.330 | 0.302 | 更大束宽下温和过滤 \(\gamma=0.15\) 最优 |
| \(b=8\) | 0.536 | 0.550 | 0.480 | 0.434 | 0.364 | 0.292 | 0.300 | 相比基线持续提升,过强过滤导致掉点 |
关键发现¶
- 置信度过滤显著改善准确率与算力权衡:在真实模型实验中,Empirical CF-Beam 在比 Vanilla-Beam 消耗更少查询预算(16.2k vs. 18.6k)的情况下,准确率反而提升了 1.6 个百分点;相比序列级最强基线 Best-of-N,准确率大幅提高 5.6 个百分点。
- 长推理链下抗衰减能力显著:在合成模拟器实验中,当推理步长 \(L\) 从 2 递增至 40 时,Best-of-N、Majority Voting 以及 Best-of-Majority 的准确率因序列级覆盖度 \(\overline{C}(x)\) 的几何恶化而发生雪崩式暴跌;而基于步级修剪的束搜索表现出极强的鲁棒性,CF-Beam 始终保持最高准确率,验证了其多项式级别复杂度缩放的理论优越性。
- 高难度稀疏覆盖任务优势最大:在模拟器单次生成成功率从 \(p=0.3\) 降至极困难的 \(p=0.01\) 时,Vanilla-Beam 和序列级基线受限于长尾采样波动准确率剧降,而 CF-Beam 依然保持显著的性能优势。
亮点与洞察¶
- 首个关于束搜索测试时缩放的严格理论刻画:填补了测试时计算领域对步级修剪机制缺乏严密统计理论保证的空白,严格确立了朴素束搜索面临的二次方覆盖度样本复杂度下界 \(\Omega(C^\star(x)^2)\)。
- 从指数级到多项式级的本质突破:明确证明了分步置信度过滤能够将搜索误差的累积控制在单步最坏覆盖度 \(C_{\max}^\star\) 和步长多项式阶内,从根本上克服了序列级推断方法无法避免的序列联合覆盖度指数增长瓶颈。
- 极简且即插即用的经验自适应过滤:提出的经验过滤准则 \(\beta_t(s) = \gamma \max_a \hat{\pi}(a \mid s, x)\) 完全摆脱了对最优路径理论逆概率的先验依赖,在实际推断中无需重训模型即可直接嵌入现有推理管道。
局限与展望¶
- 强依赖前缀似然与最终奖励的对齐性:理论推导与实验有效性均建立在假设 3(前缀竞争性)之上,即模型自身内部的自回归对数似然必须与最终真实奖励保持正相关;若模型存在严重的局部欺骗性(如高置信度幻觉),前缀可能在到达终点前被误剪枝。
- 离散硬阈值对超参数选择较为敏感:消融实验显示过大的过滤系数 \(\gamma \geq 0.6\) 会因剪裁过于激进导致性能大幅下滑,未来需要研究根据局部熵自适应调节阈值的动态机制。
- 中间步缺乏细粒度过程验证器支持:当前框架仅在末尾调用结果验证器,未来可进一步拓展至支持中间步过程奖励模型(PRM)接入的泛化束搜索理论。
相关工作与启发¶
- vs Best-of-N (Huang et al., 2025):Best-of-N 在完整生成后评估序列,样本复杂度直接受制于全路径覆盖系数 \(\overline{C}(x)\),在长链复杂推理中计算开销呈指数级恶化;本文 CF-Beam 通过逐级过滤,将搜索计算复杂度的主导项降至与步长呈多项式关系。
- vs Best-of-Majority (Di et al., 2025):Best-of-Majority 在序列级别结合多数投票与奖励模型筛选,但其自洽性保证依然受限于整句维度的采样频率;CF-Beam 将自洽性检验前移至每个 Token 步骤的局部采样分布,更早且更低成本地阻断了错误推理链。
- vs 启发式树搜索 (AlphaZero-like LLM Search / Feng et al., 2023):传统树搜索方法高度依赖密集的蒙特卡洛树评估或过程奖励模型;本文提供了极简的、仅需内部经验频数即可运作的置信度过滤机制,并给出了严格的极小化极大遗憾界证明。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从统计理论上严密证明了束搜索在测试时缩放中的多项式计算优势,并指出了朴素束搜索的理论缺陷。
- 实验充分度: ⭐⭐⭐⭐ 兼顾了理想理论假设的合成 LLM 模拟器与基于 Qwen3/AceMath 的真实大模型矩阵推理实验。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完整,问题阐述与直觉解释层次清晰,逻辑闭环极强。
- 价值: ⭐⭐⭐⭐⭐ 为当前火热的推理模型(如 o1 类系统)在测试时算力扩展策略的设计提供了坚实的理论基石。