Power sampling no longer takes one step per call: prefetching the accept/reject subtree cuts PowerMH time by a median 1.71×

Test-time power sampling no longer advances one MH transition at a time. PreSTO treats future accept/reject outcomes as a tree, generates the feasible proposals of a prefetched subtree in one batched model call, and then follows the realized path with the original MH acceptance rule. Previously each PowerMH proposal had to wait for the previous accept/reject outcome to fix the next state, so one model call completed exactly one MH transition. Across 105 sampler, LLM, and dataset settings, PreSTO reaches median speedups of 1.71× over PowerMH, 1.91× over EntropyCut, and 2.33× over MultiTryMH, and is never slower than its baseline in any setting.

The speedup comes from fewer model calls rather than cheaper ones. Each PreSTO call completes several MH transitions, so the number of calls falls while each call grows longer because it batches several proposals. A PowerMH call completes one transition; on LCB V6 with Qwen3.5-9B, PreSTO-PowerMH completes 4.96 transitions per call, makes 4.92× fewer calls, and each call takes 3.42× as long. On LCB V6 with Qwen3.5-9B, PreSTO-PowerMH finishes 100 transitions in 375.12±35.08 seconds against 539.24±30.92 seconds for PowerMH, a 1.44× speedup in cumulative model-call time.

Which proposals to prefetch is decided by prediction rather than spread uniformly. The authors observe that MH reaches only a sparse, nearly unary part of the prefetched subtree, so a classifier predicts each candidate request's certainty class and dynamic programming picks the subtree that maximizes predicted completed transitions within the budget. The default breadth-first traversal expands decisions regardless of how likely MH is to reach them, spending part of the budget on nodes MH rarely visits. On LCB V6 with Qwen3.5-9B, the predictive traversal rule is 1.25×–1.37× faster than breadth-first at all five prefetch budgets tested, and faster on 98 of the 100 prompt–budget pairs.

The report covers the acceleration of PreSTO applied to three serial MH samplers, PowerMH, EntropyCut, and MultiTryMH, evaluated on seven datasets and five base LLMs, using the first 20 prompts of each dataset, a fixed 1024-token response length, and 100 realized MH transitions. It is intended for researchers and engineers who use or evaluate power-sampling inference and care about inference latency and memory use.

The authors report that the predictive traversal rule realizes more transitions in 11 of the 20 prompt–budget pairs and fewer in 8, so its speedup is an average over all trees rather than a gain on every tree. Equivalence holds in 29 of 38 tests, and in the remaining comparisons the 90% intervals extend past the 0.2-baseline-standard-deviation margin. The link between the fraction of certain decisions and transitions per call is described by the authors as correlational, because the histograms count all scored decisions rather than realized acceptances.