Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding¶

会议: NeurIPS 2025
arXiv: 2503.01422
代码: https://github.com/Alsace08/ST-BoN
领域: LLM推理 / 测试时计算
关键词: Best-of-N, test-time scaling, early truncation, latent consistency, token efficiency

一句话总结¶

提出 Self-Truncation Best-of-N (ST-BoN) 解码方法，通过理论证明早期隐状态一致性可预测最终一致性，在生成早期就识别并截断次优样本，实现降低80%+内存和50%延迟的同时保持BoN性能。

研究背景与动机¶

领域现状：Best-of-N (BoN) 采样是常用的test-time scaling方法——生成N个候选回答，用奖励模型或自一致性选最优。BoN能有效利用模型分布中的优质解。
现有痛点：(a) 全量生成N个完整样本占用大量GPU内存（KV cache线性增长），限制了可用N的大小；(b) 奖励模型额外占用显存和推理时间，且训练强RM成本高、泛化性差。现有改进方法（如FastRM、TreeBoN）仅解决单一挑战。
核心矛盾：BoN的效率瓶颈来自"必须生成完整的N个样本+使用外部RM评分"这两个假设——能否更早判断哪个样本最有希望？
本文要解决什么？ 在生成早期自主判断最有前途的样本，截断其余样本，无需外部RM。
切入角度：自一致性的核心洞察是"多条推理路径趋向同一答案则该答案更可靠"——如果早期隐状态的一致性已经能预测最终一致性，就可以在早期做截断。
核心idea一句话：用LLM自身隐状态的Chain-of-Embedding特征度量采样间一致性，在首次分叉时刻就预测最终最优样本并截断其余。

方法详解¶

整体框架¶

ST-BoN的三步流程：(1) 并行生成N个样本直到最早分叉时刻 \(c\)（所有样本序列两两不同）；(2) 继续生成 \(\tau\) 步，在每步用隐状态一致性自评估各样本质量，投票选出最有前途的样本；(3) 截断其余 \(N-1\) 个样本，仅完成最优样本的生成。

关键设计¶

理论基础：早期一致性预测最终一致性 (Theorem 1):
做什么：证明早期采样距离小的样本在生成结束时也更可能保持接近
核心思路：设 \(S_t = \sum_i d_t^i\) 为时刻 \(t\) 的总距离。在local Lipschitz连续和bounded increment假设下，\(\mathbb{E}[S_{t+1}] \leq \Gamma \cdot S_t\)，其中 \(\Gamma = 1+LM\)。Markov不等式给出 \(\Pr[S_T \leq \epsilon | S_t] \geq 1 - \frac{\Gamma^{T-t}}{\epsilon} S_t\)
设计动机：为在早期截断提供理论保证——不只是启发式，而是概率可控的
Chain-of-Embedding (CoE) 隐状态一致性度量:
做什么：用LLM内部隐状态表示的"潜在思维路径"的曲率来度量样本间差异
核心思路：对每个样本，提取各层隐状态的句子嵌入 \(\mathbf{h}_l^T\)，计算跨层的normalized Manhattan距离和角距离之差 \(\mathcal{F}(\mathbf{H})\)。样本间距离 \(\mathcal{D}(Y^i, Y^j) = (\mathcal{F}(\mathbf{H}^i) - \mathcal{F}(\mathbf{H}^j))^2\)。选 \(\mathcal{D}\) 最小的样本（最一致的）
设计动机：在生成早期，文本差异极微小，基于输出token难以区分；隐状态包含更丰富的语义信息，能捕捉到未体现在token level的推理路径差异
Buffer Window 稳健估计:
做什么：在buffer window \([c, c+\tau]\) 内多次投票，降低单时刻估计的随机性
核心思路：\(\tau = m \cdot c\)（默认 \(m=1\)），每步独立选最优样本，最终取多数投票结果
设计动机：分叉点 \(c\) 处差异刚出现，可能不够显著；缓冲窗口给时间让差异积累

损失函数/训练策略¶

ST-BoN是training-free的推理方法，无需训练，直接在解码时使用。

实验关键数据¶

主实验¶

四个客观任务（MATH, TheoremQA, GPQA, MMLU）+ 两个主观任务（CNNDM, AlpacaFarm），三个模型:

方法	内存减少	延迟减少	性能
Full-BoN w/o RM (self-consistency)	基线	基线	基线
Full-BoN w/ RM (PRM)	更高（加载RM）	更高	通常最优
ST-BoN	>80%	~50%	≈ Full-BoN w/o RM

达到Full-BoN相同性能时的计算节省： | 模型 | 任务 | Full-BoN所需N | ST-BoN等效N | 计算节省 | |------|------|-------------|------------|---------| | Llama3-8B | MATH | N=16 | N=64 ST-BoN ≈ N=16 Full | 70-80% | | Qwen2.5-7B | MATH | N=16 | 类似 | 70-80% |

相同计算成本下的性能提升： | 模型 | 任务 | Full-BoN Acc | ST-BoN Acc | 提升 | |------|------|------------|-----------|------| | Llama3-8B | MATH | 50.2% (N=8) | 53.4% | +3.2 | | Qwen2.5-7B | TheoremQA | 46.8% (N=8) | 50.1% | +3.3 |

消融实验¶

配置	效果	说明
\(\tau=0\) (无buffer)	性能下降2-3%	需要缓冲窗口稳定估计
\(m=0.5\) vs \(m=1\) vs \(m=2\)	\(m=1\)最优	太短不稳定，太长浪费成本
CoE vs output token距离	CoE显著更优	隐状态比输出token更具判别性
72B模型	依然有效	跨模型规模泛化

关键发现¶

分叉时刻 \(c\) 通常在生成长度 \(T\) 的5-10%处——截断窗口在非常早期就关闭
GPU内存节省随N增大而增加，N≥5时节省超80%
ST-BoN在主观任务（摘要、指令跟随）上也有效，说明CoE一致性的通用性
与PRM相比，ST-BoN在不需要任何外部模型的情况下达到接近的性能

亮点与洞察¶

理论+实践的优雅闭环：先证明早期一致性→最终一致性的概率保证，再用CoE设计实用度量，最后用buffer window弥补估计方差。每一步都有清晰的motivation
彻底消除RM依赖：在不使用任何外部奖励模型的前提下，用模型自身隐状态做"自验证"，真正做到了plug-and-play
实际部署价值：80%+内存节省+50%延迟减少对LLM推理服务意义重大——同样的GPU可以处理更多请求或使用更大的N

局限性 / 可改进方向¶

CoE特征的计算需要提取所有层的隐状态，在某些推理框架（vLLM等）中可能不方便
对于推理型任务效果好，但对于创意生成等多样性重要的任务，截断可能损失有价值的多样性
理论中的Lipschitz常数和bounded increment假设在实际LLM中的适用性需要进一步验证
仅与self-consistency和PRM比较，未与其他效率方法（如speculative decoding）对比

评分¶

新颖性: ⭐⭐⭐⭐ 早期隐状态一致性预测最终表现的想法新颖，有理论支撑
实验充分度: ⭐⭐⭐⭐⭐ 六个数据集、四个模型（含72B）、多维度消融，非常充分
写作质量: ⭐⭐⭐⭐ 理论-方法-实验的逻辑链清晰，但部分主方法的呈现可以更紧凑
价值: ⭐⭐⭐⭐⭐ 高度实用——不需要训练任何模型，即插即用，节省大量推理资源