PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling

arXiv:2610.13171v1 Announce Type: new 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 extit{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 extit{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.71imes, 1.91imes, and 2.33imes on PowerMH and its follow-ups EntropyCut and MultiTryMH, respectively; on the first two, it makes a median of 3.9imes fewer model calls, each only 2.1imes longer. On LCB V6 with Qwen3.5-9B, the predictive traversal rule is a further 1.25imes--1.37imes faster than the default breadth-first traversal.

Related

• Chopthin-Consensus Power Sampling: A Diversity-Preserving Approach to LLM Decoding
• When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
• Self-Consistency via Marginal Sharpening

Source: arXiv cs.CL | 2026-10-12