PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling

📄 arXiv: 2610.13171v1 📥 PDF

作者: Nan Jiang, Panagiotis Theodoropoulos, Wei Deng

分类: cs.CL

发布日期: 2026-10-09

💡 一句话要点

提出PreSTO以加速LLM的PowerMH采样

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 Power采样 Metropolis-Hastings 预测子树 加速采样 自然语言处理 智能助手

📋 核心要点

  1. 现有的PowerMH采样方法由于其顺序更新机制，导致采样速度较慢，影响了LLM的推理效率。
  2. 本文提出的PreSTO方法通过预取未来提案，利用预测子树的方式加速了PowerMH采样过程，保持了MH转移核的不变性。
  3. 实验结果显示，PreSTO在多个数据集上实现了1.71倍至2.33倍的速度提升，并显著减少了模型调用次数。

📝 摘要（中文）

Power采样通过从基础模型的分布中采样其锐化版本来提高大型语言模型（LLM）在测试时的推理能力。然而，PowerMH采样器由于其Metropolis-Hastings（MH）更新是顺序的，导致速度较慢。为了解决这一问题，本文提出了预测子树预取（PreSTO），通过预取未来的提案来加速PowerMH，同时保持其MH转移核不变。PreSTO将未来的MH结果视为接受/拒绝决策的树，在每次模型调用中生成一个预取子树的提案，并根据原始MH接受规则跟随实现的路径。实验结果表明，PreSTO在七个数据集和五个基础LLM上实现了显著的速度提升。

🔬 方法详解

问题定义：本文旨在解决PowerMH采样器在大型语言模型推理时的速度瓶颈，现有方法的顺序更新机制导致采样效率低下。

核心思路：提出预测子树预取（PreSTO）方法，通过预取未来的提案来加速采样过程，同时确保MH转移核不变，从而提高采样效率。

技术框架：PreSTO的整体框架包括生成一个接受/拒绝决策树的预取子树，在每次模型调用中批量生成提案，并根据MH接受规则跟随实现的路径。

关键创新：PreSTO的核心创新在于将MH结果视为决策树，并设计了预测遍历规则，以最大化完成转移的预期数量，这与现有方法的顺序采样机制形成了鲜明对比。

关键设计：在设计中，PreSTO通过选择最优的子树进行遍历，进一步提高了采样速度，特别是在使用Qwen3.5-9B模型时，预测遍历规则比默认的广度优先遍历快1.25倍至1.37倍。

🖼️ 关键图片

fig_0
img_1
img_2

📊 实验亮点

实验结果表明，PreSTO在PowerMH及其后续方法EntropyCut和MultiTryMH上实现了1.71倍至2.33倍的速度提升，同时在前两者上减少了3.9倍的模型调用次数，每次调用仅增加2.1倍的时间。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、对话系统和智能助手等，能够显著提升大型语言模型在实时推理中的效率，具有广泛的实际价值和未来影响。

📄 摘要（原文）

Power sampling improves large language model (LLM) reasoning at test time by sampling from a sharpened version of the base model's distribution. Its sampler, PowerMH, is slow because its Metropolis--Hastings (MH) updates are sequential: each accept/reject decision sets the state from which the next proposal is generated. Prior work reduces this cost by changing the sampler or the model (e.g., sequential Monte Carlo, approximate lookahead, distillation). We propose Predictive SubTree Prefetching (PreSTO), which accelerates PowerMH by prefetching future proposals and provably leaves its MH transition kernel unchanged. PreSTO views future MH outcomes as a tree of accept/reject decisions: in each model call, it generates the proposals of a \textit{prefetched subtree} of this tree in one batch, then follows the realized path with the original MH acceptance rule. We also observe that MH reaches only a sparse, nearly unary part of each prefetched subtree, we further design a \textit{predictive traversal rule} that chooses the subtree to maximize the predicted number of completed transitions. Across seven datasets and five base LLMs, PreSTO achieves median speedups of $1.71\times$, $1.91\times$, and $2.33\times$ on PowerMH and its follow-ups EntropyCut and MultiTryMH, respectively; on the first two, it makes a median of $3.9\times$ fewer model calls, each only $2.1\times$ longer. On LCB V6 with Qwen3.5-9B, the predictive traversal rule is a further $1.25\times$--$1.37\times$ faster than the default breadth-first traversal.