Reasoning with Sampling: Cutting at Decision Points

会议: NeurIPS 2026
arXiv: 2605.30327
OpenReview: https://openreview.net/forum?id=Mp3rA04Yjp
领域: 其他
关键词: 幂分布采样, Metropolis-Hastings, 熵跃变, 决策点, 推理混合时间

一句话总结

针对基础语言模型无须后训练即可通过幂分布采样激发推理能力但现有 MCMC 采样混合极慢的难题，本文提出了决策点熵跃变 Metropolis–Hastings 采样算法（Entropy-Cut MH），利用下一个 token 的正向熵跃变自适应定位关键决策分叉并重采后缀，从理论上将马尔可夫链混合时间由依赖全文 token 长度的 \(\mathcal{O}(T)\) 降至仅依赖语义决策深度的 \(\mathcal{O}(k)\)，在数学、代码与科学推理基准上全面超越现有采样基线与等预算 Best-of-N。

研究背景与动机

前沿大语言模型的强大推理能力通常归功于基于强化学习（RL）的后训练过程，但这引发了一个基础性科学问题：强化学习到底赋予了模型全新的推理程序，还是仅仅激活了基础预训练模型中早已编码的潜能？越来越多的实证研究支持所谓的“锐化假说”（sharpening view），即基础模型在生成空间中本就为高质量的正确推理链赋予了不可忽视的概率质量，后训练的作用本质上是将分散在 top-\(k\) 的候选轨迹质量集中到 top-1，而非凭空创造此前不存在的推理模式。基于这一洞察，近期工作证明直接对基础模型序列概率分布进行“幂分布”（power distribution, \(\Pi_T(x) \propto p(x)^\alpha\)）锐化采样，无需任何额外训练参数、标注数据或验证器（verifier），便能激发与强化学习相当的强推理表现。

然而，从全局归一化的幂分布中高效采样面临着极其严苛的计算挑战。由于序列空间随长度呈指数级膨胀，解析计算配分函数完全不可行，现有方法只能退守到分阶段的 Metropolis–Hastings（MH）马氏链蒙特卡洛算法。在这类采样器中，链能否快速混合取决于其在不同推理模式（modes）之间的跨越能力——例如从“归纳证明”切换至“反证法”。然而，现有分阶段 MH 采样器在每次提议时完全以均匀随机分布（uniform cut）选择剪切位置。因为一条漫长的推理轨迹中通常只包含寥寥数个至关重要的全局决策（如算法设计、分步策略或定理选择），其余绝大多数 token 都只是机械执行后续的符号运算与中间推导，均匀采样有极高概率剪切在局部运算的末端，导致采样器反复在同一分支内微调细枝末节，陷入难以逃脱低电导率（low conductance）瓶颈的慢混合陷阱。

本文的切入点在于破除对 token 序列均匀平铺的机械假设，利用基础模型自身的内生信号精准捕捉高阶语义决策的发生位置。作者敏锐地发现，在推理轨迹的分叉节点，模型面临多种可行动向的抉择，其下一个 token 的条件分布预测不确定性必然急剧上升，而正向熵跃变（positive entropy jump）恰恰是捕捉决策分水岭的无监督天然探针。核心 idea：提出基于决策点熵跃变的 Metropolis–Hastings 采样算法（Entropy-Cut MH），以模型下一个 token 的正向熵跃变大小自适应重构剪切位置分布，使 MCMC 提议精准回溯至关键分叉节点并重构后续解题路径，在保证平稳分布严格不变的前提下，将马尔可夫链混合时间从依赖全文 token 长度的 \(\mathcal{O}(T)\) 大幅降阶为仅取决于语义决策深度的 \(\mathcal{O}(k)\)。

方法详解

整体框架

本文方法以提示词 \(x_P\) 与基础自回归语言模型 \(p\) 为输入，目标是高效抽取服从全局序列幂分布 \(\Pi_T(x) \propto p(x)^\alpha\) 的完整解答序列 \(x_{0:T}\)。为避免从头生成长序列导致的严重冷启动问题，算法采用分阶段（stagewise）推进策略：按固定块大小 \(B\) 将目标长度逐步从 \(T_1=B\) 增长至 \(T_K=T\)。在每一个长度阶段 \(k\)，算法以当前前缀初始化候选轨迹，随后运行 \(N_{\text{MCMC}}\) 步 Metropolis–Hastings 转移迭代。每一步迭代中，模型在前向计算对数似然的同时获取 token 级条件熵，识别出熵增剧烈的决策点并依概率分布选取剪切位置 \(m\)；保留剪切点前的前缀后，利用低温提议分布重绘后续 tokens，最后借助包含状态转移矫正因子的 Hastings 接受率判定是否更新当前状态。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：提示词与基础自回归模型分布"] --> B["分阶段前向扩展<br/>按块步长递增目标长度抑制冷启动"]
    B --> C["决策点熵跃变剪切法则<br/>计算正向熵增并自适应采样剪切点"]
    C --> D["后缀重采样提议<br/>基于低温提议模型重绘候选后缀"]
    D --> E["状态依赖剪切的 MH 精确修正机制<br/>计算修正接受率并执行状态转移判定"]
    E --> F["推理树快速混合收敛<br/>以 O(k) 步长逼近全局目标幂分布"]

关键设计

1. 决策点熵跃变剪切法则：以不确定性突增定位分叉节点 针对均匀剪切策略往往剪在细枝末节、无法回退至核心决策点的问题，该设计旨在建立一种无需任务特定先验的通用决策点识别准则。对于给定前缀 \(x_{<t}\)，基础模型在词表 \(V\) 上的下一个 token 预测香农熵定义为 \(h_t(x) = -\sum_{v \in V} p(v \mid x_{<t}) \log p(v \mid x_{<t})\)。如果直接以 \(h_t(x)\) 作为采样权重，由于做出重大决定后模型往往需要连续几个 token 来展开逻辑，局部区域的熵值会持续偏高，导致剪切概率被分散到决策后的整个长尾区间。为此，本文设计了正向熵跃变指标：

\[\Delta_t(x) \coloneqq \max\left\{0,\, h_t(x) - h_{t-1}(x)\right\} \quad (1 \leq t \leq \ell)\]

该指标精确响应模型不确定性“刚刚发生陡增”的起始瞬间，抑制了处于高熵平台期但已落入后续执行细节的次要位置。在此基础上，定义带温度调节系数 \(\beta \geq 0\) 的剪切位置分布：

\[\lambda_\beta(m; x) \propto \Delta_m(x)^\beta \quad (1 \leq m \leq \ell)\]

当 \(\beta=0\) 时，该分布自然退化为经典的均匀剪切分布；随着 \(\beta\) 增大，采样质量高度集中在发生最大熵跃变的关键决策点。在所有位置均无熵增的平坦边界情况下，算法安全平滑地回退至均匀分布。

2. 状态依赖剪切的 MH 精确修正机制：保证全局平稳分布不产生统计偏差 当提议机制引入了依赖当前轨迹状态的剪切概率分布 \(\lambda_\beta(m; x)\) 时，朴素的提议对称性被打破。如果仍沿用均匀剪切的简单接受率，马尔可夫链的平稳分布必然偏离目标幂分布 \(\Pi_T\)。为了在剧烈改变提议流向的同时保持理论上的严格无偏，必须将状态依赖的剪切选择概率纳入 Hastings 修正项。

对于当前状态 \(x\) 与剪切位置 \(m\) 处由低温提议分布 \(p_{\text{prop}}\) 采出的候选轨迹 \(x^{\text{prop}} = (x_{0:m-1}, s)\)，其双向提议转移概率不仅包含后缀生成的自回归概率，还显式乘上了在各自状态下选中该剪切点 \(m\) 的概率。因此，精确的 Metropolis–Hastings 接受概率被推导为：

\[A_m(x, x^{\text{prop}}) = \min\left\{1,\, \frac{p(x^{\text{prop}})^\alpha}{p(x)^\alpha} \cdot \frac{\lambda_\beta(m; x^{\text{prop}})}{\lambda_\beta(m; x)} \cdot \frac{p_{\text{prop}}(x_{m:T_k} \mid x^{\text{prop}}_{0:m-1})}{p_{\text{prop}}(x^{\text{prop}}_{m:T_k} \mid x_{0:m-1})}\right\}\]

值得强调的是，计算序列未归一化幂概率 \(p(x)^\alpha\) 本身就需要对轨迹执行前向计算，而各位置的条件熵 \(h_t(x)\) 与跃变值 \(\Delta_t(x)\) 可在同一前向 pass 中直接从输出 logits 伴随得出。因此，相比均匀剪切基线，引入状态依赖的精确修正机制完全不消耗额外的模型推理前向计算开销。

3. 推理树快速混合收敛：将马氏链混合时间从 \(\mathcal{O}(T)\) 降低至 \(\mathcal{O}(k)\) 针对长序列空间下 MCMC 混合时间呈指数或长多项式爆炸的理论痛点，本文在简化的“推理树”（Reasoning Tree）模型下建立了严格的收敛性保证。将生成空间建模为深度为 \(T\) 的根至叶路径，路径上的节点被形式化划分为两类：存在多个分支选择的“分支节点”（branch node，对应语义决策）与只有唯一确定后继的“链节点”（chain node，对应确定性推导）。设一条路径上的分支节点总数为 \(k\)（即语义深度），首个分支节点出现在深度 \(b_1 \leq T/2\) 处。

由于均匀剪切随机洒在长度为 \(T\) 的整个序列上，其击中位于前部的关键分支节点 \(b_1\) 的概率仅为 \(\mathcal{O}(b_1/T)\)，导致马尔可夫链在不同宏观解题策略之间的跨越电导率（conductance）极低，其全变差距离收敛至 \(\varepsilon\) 所需的均匀混合时间下界为：

\[\tau_{\text{mix}}^{\text{unif}}(\varepsilon) = \Omega_\varepsilon\left(\frac{T}{b_1}\right) = \Omega(T) \quad (\text{当 } b_1 = \mathcal{O}(1))\]

而 Entropy-Cut 机制将剪切概率全部收束到 \(k\) 个发生正向熵跃变的分支节点上，使得状态在各主要推理模式之间的有效转移电导率提升为 \(\Theta(1/k)\)。在近似对称树结构下，定理 4.1 证明其混合时间上界满足：

\[\tau_{\text{mix}}^{\text{ec}}(\varepsilon) \lesssim e^{2\eta} k \log\left(\frac{1}{\varepsilon}\right) = \mathcal{O}(k)\]

这从数学上严格确立了：Entropy-Cut MH 的混合复杂度直接由推理链中的核心语义决策步数 \(k\) 决定，而非最终展开的 token 总长度 \(T\)。当长思考链中 \(k \ll T\) 时，该方法实现了巨大的收敛加速。

损失函数 / 训练策略

本方法属于完全无需训练的测试期采样增强技术（Training-Free / Verifier-Free Test-Time Scaling），无需对基础模型参数进行微调或更新，也不依赖外部奖励模型与验证器。核心超参数与采样策略如下： - 锐化幂指数: 默认设定 \(\alpha=4.0\)（在代码生成基准 HumanEval 上设为 \(\alpha=5.0\) 表现更优），实现对高置信度完整序列的全局偏置。 - 剪切温度与步长: 剪切幂指数固定为 \(\beta=4.0\)，分阶段块大小设为 \(B=192\)（对应 \(T=3072\) 时分为 16 个阶段；在更具挑战性的 GPQA Diamond 与 AIME26 上序列长度和块大小翻倍至 \(T=6144, B=384\)）。 - 提议模型与链长: 提议分布 \(p_{\text{prop}}\) 统一采用基础模型在温度 \(\tau = 1/\alpha\) 下的低温自回归采样，每个阶段固定运行 \(N_{\text{MCMC}} = 10\) 步迭代，兼顾充分混合与采样效率。

实验关键数据

主实验

在 MATH500（竞赛数学）、HumanEval（代码生成）、GPQA Diamond（专家级科学问答）与 AIME26（高难度数学奥赛）四大高难度推理基准上，本文方法（Entropy-Cut MH）全面评测了涵盖基础模型与指令微调模型在内的 5 款代表性模型，并与标准贪婪/随机采样、低温采样、序列蒙特卡洛（SMC）、扭曲蒙特卡洛（TMC）以及均匀剪切 MH 进行了系统横向对比。

模型	采样方法	MATH500 (%)	HumanEval (%)	GPQA Diamond (%)	AIME26 (%)
Qwen2.5-7B	Standard	35.9	33.0	29.4	2.0
	Low-Temperature (\(\tau=1/\alpha\))	62.3	64.3	29.5	5.7
	SMC (Power-SMC)	69.8	64.9	28.8	7.4
	TMC (Twisted-MC)	70.4	66.2	27.5	9.4
	Uniform-Cut MH	67.4	66.8	29.4	8.2
	Entropy-Cut MH (本文)	71.9	68.9	30.2	9.4
Qwen2.5-Math-7B	Standard	50.1	31.0	29.0	4.8
	Low-Temperature	68.3	55.8	33.1	6.4
	SMC	78.9	55.2	32.0	11.8
	TMC	78.2	51.2	32.5	10.6
	Uniform-Cut MH	73.1	59.8	32.4	9.5
	Entropy-Cut MH (本文)	79.0	59.9	34.1	13.1
Qwen3-8B-Base	Standard	58.5	47.6	31.7	3.2
	Low-Temperature	77.3	73.7	37.6	6.4
	SMC	79.3	76.7	38.1	10.1
	TMC	79.7	75.2	38.6	9.8
	Uniform-Cut MH	79.5	75.8	38.8	9.5
	Entropy-Cut MH (本文)	80.2	79.3	40.0	10.3
Phi-3.5-mini-instruct	Standard	42.9	40.5	27.8	0.6
	Low-Temperature	45.3	62.2	32.5	1.6
	SMC	49.8	65.2	31.0	1.7
	TMC	49.3	65.6	31.5	3.0
	Uniform-Cut MH	49.1	64.9	31.8	2.9
	Entropy-Cut MH (本文)	49.7	65.6	32.8	3.1
Phi-4-mini-instruct	Standard	55.5	39.9	30.7	3.5
	Low-Temperature	66.4	65.5	32.1	6.8
	SMC	68.1	66.7	31.9	8.6
	TMC	66.1	66.1	32.1	6.9
	Uniform-Cut MH	68.7	67.9	32.0	8.0
	Entropy-Cut MH (本文)	68.8	68.4	33.3	8.7

消融实验

下表汇总了两组关键分析数据：第一部分检验以熵跃变 \(\Delta_t\) 定位决策点的合理性（在 MATH500 上对 top-10% 与 bottom-10% 熵增位置各重采 16 次后缀测算归一化编辑距离与最终答案多样性）；第二部分在严格对齐实际消耗 token 总量（包含被 MH 拒绝的全部提议 token）的前提下，对比基于模型平均对数似然选择的最优候选（Best-of-N, BoN）。

实验类型与配置	评测指标 / 数据集	本文 / 高熵组	对照基线 / 低熵组	显著性与变化说明
决策点敏感度探针	归一化后缀编辑距离	0.287 (Top 10% \(\Delta_t\))	0.216 (Bottom 10% \(\Delta_t\))	差异达 1.33×，证明高熵增处是分叉分水岭
	独立答案比例 (Distinct Answers)	0.63 (Top 10% \(\Delta_t\))	0.47 (Bottom 10% \(\Delta_t\))	差异达 1.36×，证明重采导致解题路径真正分流
等 Token 预算 BoN (Qwen2.5-Math-7B)	MATH500 准确率 (%)	78.8 (Entropy-Cut)	75.7 (Standard BoN) / 74.4 (Low-Temp BoN)	超越 Standard BoN 3.1% (\(p=0.0004\))；超越 Low-Temp 4.4%
	HumanEval 准确率 (%)	58.9 (Entropy-Cut)	49.1 (Standard BoN) / 61.0 (Low-Temp BoN)	显著击败 Standard BoN (\(p=2.6\times 10^{-6}\))
	AIME26 准确率 (%)	13.3 (Entropy-Cut)	10.4 (Standard BoN) / 4.1 (Low-Temp BoN)	显著领先 Low-Temp BoN 9.2% (\(p=0.0313\))
等 Token 预算 BoN (Qwen3-8B-Base)	MATH500 准确率 (%)	80.1 (Entropy-Cut)	78.2 (Standard BoN) / 74.4 (Low-Temp BoN)	超越 Standard BoN (\(p=0.0225\)) 与 Low-Temp BoN

关键发现

• 混合时间质的飞跃: 在 Qwen2.5-7B 上，Entropy-Cut MH 相比均匀剪切 MH 在 MATH500 上取得 +4.5%（71.9% vs 67.4%）的显著净提升，在 AIME26 上超越均匀剪切 1.2% 并逼平最复杂的 TMC，实证验证了将剪切操作约束在分支节点带来的快速混合收益。
• 等预算计算缩放优势: 在严格对齐总前向 token 预算（将 MCMC 生成被拒 token 均计入计算预算）的公平设定下，Entropy-Cut MH 在 6 个测试设定中有 5 个显著击败低温 Best-of-N，且大幅领先标准 Best-of-N。这证明通过马尔可夫链自适应回溯探索高质量局部模态，相比单纯独立平行抽样能更有效地分配推理计算量。
• 超参数稳定性与多样性保持: 消融实验证明，算法在锐化幂次 \(\alpha \ge 2.0\)、剪切幂次 \(\beta \ge 2.0\) 以及 MCMC 步数 \(N_{\text{MCMC}} \ge 10\) 时表现极度稳健；且通过 pass@k 曲线分析发现，尽管 pass@1 大幅攀升，序列的探索多样性并未像普通低温贪婪生成那样发生崩塌。

亮点与洞察

• 将语义分叉无缝映射为熵导数: 巧妙利用条件熵正向一阶差分 \(\Delta_t\) 作为决策点代理指标，既规避了解析推理树结构所必需的人工规则干预，又避免了高熵延展区间的质量稀释，实现了无监督的端到端决策点自适应定位。
• 无额外前向开销的理论保真修正: 状态依赖剪切概率的比值被无缝代入 Hastings 修正因子，直接复用似然评估过程中已算出的 logits 缓存，在零附加模型调用成本的前提下严格保证了对全局幂分布的理论无偏收敛。
• 推理能力提炼范式的重估: 再次强有力地证实了基础模型中存在未被充分释放的潜在推理结构；无需昂贵的 RLHF 或过程奖励模型，纯粹通过数学上良好定义的序列级幂分布采样，即可激发出顶尖的数学与代码推理水平。

局限与展望

• 作者承认的局限: 当前实验主要集中在 7B-8B 规模的中小型开源模型上，尚未在千亿参数量级模型或专有超大底模上验证其边际收益；同时本方法主要针对单次完整响应生成（single-shot completion），尚未扩展到包含显式多轮交互、外部工具调用或动态分支验证的复合 agent 架构中。
• 实际观察到的局限: 算法尽管混合速度快于均匀剪切，但分阶段 MH 的固有串行依赖结构仍带来了一定的解码延迟，其端到端生成耗时明显高于简单的低温采样；此外，在部分结构化格式要求极高的任务中，过度回溯可能破坏局部排版一致性。
• 具体改进思路: 可探索将决策点熵跃变检测机制与推测解码（speculative decoding）或树状注意力并行加速技术结合，在并发分支上执行剪切验证，以摊平 MCMC 的串行延迟壁垒。

相关工作与启发

• vs Uniform-Cut MH (Karan & Du, ICLR 2026): 二者均基于分阶段 Metropolis–Hastings 框架逼近全局幂分布，但均匀剪切在长文本推导中大概率剪在确定性计算片段导致混合停滞；本文引入正向熵跃变引导剪切，将混合时间从序列长度 \(\mathcal{O}(T)\) 解耦至决策深度 \(\mathcal{O}(k)\)。
• vs Sequential Monte Carlo (Power-SMC, Azizi et al., 2026): Power-SMC 采用粒子滤波（particle filtering）在自回归生成的每一步动态维护粒子加权与重采样；本文保留了 MCMC 框架，无需在显存中常驻维护高维粒子群，实现机制更为精炼且易于部署。
• vs Twisted Monte Carlo (Ji et al., 2026): TMC 需要借助价值网络或近似扭曲函数估计未来补全概率，计算与实现成本极高（耗时约双倍于普通采样）；本文完全不需要学习外部价值扭曲，仅凭基础模型自身的内生熵跃变即可实现更优的推理性能。

评分

• 新颖性: ⭐⭐⭐⭐⭐ [将熵导数作为 MCMC 剪切转移的自适应代理，打破了序列长依赖混合瓶颈，理论分析与算法设计高度自洽]
• 实验充分度: ⭐⭐⭐⭐⭐ [跨越 5 个主流模型与 4 大权威推理基准，全面涵盖与各类蒙特卡洛基线及等计算预算 Best-of-N 的对照分析]
• 写作质量: ⭐⭐⭐⭐⭐ [逻辑链条清晰严密，从现象洞察到理论模型抽象再到工程落地的过渡自然流畅]
• 价值: ⭐⭐⭐⭐⭐ [为免训练、免验证器的测试期计算缩放（Test-Time Scaling）与基础模型潜在推理能力激发开辟了高效实用的新途径]

相关论文

• [NeurIPS 2026] Power Distribution Bridges Sampling, Self-Reward RL, and Self-Distillation
• [ICML 2026] Reasoning Can Be Restored by Correcting a Few Decision Tokens
• [ICLR 2026] Reasoning with Sampling: Your Base Model is Smarter Than You Think
• [ICLR 2026] Beyond Speedup - Utilizing KV Cache for Sampling and Reasoning
• [ACL 2025] DeFine: Decision-Making with Analogical Reasoning over Factor Profiles