arXiv cs.CL· Nan Jiang, Panagiotis Theodoropoulos, Wei Deng·· 6 天前AI 评分22
PreSTO：面向快速 LLM Power Sampling 的预测性子树预取
PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling
AI 导读
PreSTO 通过预取未来提议来加速 PowerMH 采样器，且可证明不改变其 MH 转移核。在七个数据集和五个基础 LLM 上，PreSTO 对 PowerMH、EntropyCut 和 MultiTryMH 分别取得 1.71×、1.91× 和 2.33× 的中位加速，前两者模型调用次数中位数减少 3.9×，每次调用仅延长 2.1×。
正文 · 原文
Abstract: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.
| Subjects: | Computation and Language (cs.CL) |
| Cite as: | arXiv:2610.13171 [cs.CL] |
| (or arXiv:2610.13171v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2610.13171 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Nan Jiang [view email]
[v1]
Fri, 9 Oct 2026 07:58:06 UTC (2,788 KB)
来源：arXiv cs.CL · arxiv.org