Glonce

PreSTO prefetching speeds up LLM power sampling by a median 1.7x to 2.3x

researchThe Glonce editorsHugging Face🔥64Glonce rating64Impact55Novelty65Relevance100Surprise35Players10Credibility80
PreSTO prefetching speeds up LLM power sampling by a median 1.7x to 2.3x

Power sampling is a way to improve large language model reasoning at test time: instead of sampling from the base model's distribution directly, it samples from a sharpened version of it. Its sampler, PowerMH, is slow because it relies on Metropolis-Hastings (MH) updates that are sequential. Each accept/reject decision sets the state from which the next proposal is generated, so the work cannot simply be run in parallel.

Prior work attacks this cost by changing the sampler or the model, for example with sequential Monte Carlo, approximate lookahead or distillation. The paper takes a different route. It proposes Predictive SubTree Prefetching (PreSTO), which accelerates PowerMH by prefetching future proposals and, according to the authors, provably leaves the MH transition kernel unchanged.

The idea is to view future MH outcomes as a tree of accept/reject decisions. In each model call, PreSTO generates the proposals of a prefetched subtree of that tree in one batch, then follows the realized path through it using the original MH acceptance rule. The authors also observe that MH reaches only a sparse, nearly unary part of each prefetched subtree, so they design a predictive traversal rule that chooses the subtree to maximize the predicted number of completed transitions.

On results, the paper reports that across seven datasets and five base LLMs, PreSTO achieves median speedups of 1.71x on PowerMH, 1.91x on EntropyCut and 2.33x on MultiTryMH, the latter two being follow-ups to PowerMH. On the first two methods, PowerMH and EntropyCut, it makes a median of 3.9x fewer model calls, each only 2.1x longer. In a separate comparison on LCB V6 with Qwen3.5-9B, the predictive traversal rule is a further 1.25x to 1.37x faster than the default breadth-first traversal.

Key facts

  • PreSTO (Predictive SubTree Prefetching) speeds up the PowerMH sampler by generating the proposals of a prefetched subtree of the accept/reject tree in one batch per model call.
  • The authors state it provably leaves the Metropolis-Hastings transition kernel unchanged, unlike prior work that changes the sampler or the model.
  • Across seven datasets and five base LLMs, median speedups are 1.71x on PowerMH, 1.91x on EntropyCut and 2.33x on MultiTryMH.
  • On PowerMH and EntropyCut it makes a median of 3.9x fewer model calls, each only 2.1x longer.
  • On LCB V6 with Qwen3.5-9B, the predictive traversal rule is a further 1.25x to 1.37x faster than default breadth-first traversal.

Why it matters

Power sampling lifts LLM reasoning at test time, but its PowerMH sampler is slow because each Metropolis-Hastings accept/reject decision must finish before the next proposal can be generated. Earlier speedups came from changing the sampler or the model. PreSTO instead keeps the sampler's transition kernel as it is and recovers speed by batching work, which makes it a different kind of fix from sequential Monte Carlo, approximate lookahead or distillation.

Who it affects

Researchers and engineers who run power sampling or its follow-ups, EntropyCut and MultiTryMH, to get better reasoning out of a base LLM at inference time. The paper evaluates on seven datasets and five base LLMs, and it names LCB V6 with Qwen3.5-9B for the traversal-rule comparison.

How to use it

The abstract describes a method rather than a product. In each model call, generate the proposals of a prefetched subtree of the accept/reject tree in one batch, then follow the realized path with the original MH acceptance rule. A predictive traversal rule chooses which subtree to prefetch so as to maximize the predicted number of completed transitions. No code or model release is mentioned.

How solid is it

The claims are the authors' own, drawn from the paper's abstract, which names no authors or institutions. The unchanged transition kernel is presented as provable. The speedups are medians across seven datasets and five base LLMs and are relative figures only; no absolute wall-clock times or hardware are given. The 3.9x fewer calls and 2.1x longer calls are stated for PowerMH and EntropyCut, not for MultiTryMH.

Risks and caveats

The abstract does not report effects on answer accuracy or reasoning quality of PreSTO outputs beyond the claim that the MH transition kernel is unchanged. Speedups differ by method, from 1.71x to 2.33x, and the 1.25x to 1.37x gain from the traversal rule was reported on one benchmark and model pair (LCB V6 with Qwen3.5-9B). Fewer but longer model calls also means each call does more work, so the gain depends on batching being cheap.

“accelerates PowerMH by prefetching future proposals and provably leaves its MH transition kernel unchanged”

— PreSTO paper abstract