PreSTOPredictive SubTree Prefetching for Fast LLM Power Sampling

  • University of Texas at El Paso
  • Georgia Institute of Technology
  • Morgan Stanley
Recorded subtree: prompt 0, tree 1Node v0, cut index 1024v0Node v1, cut index 1020v1Node v2, cut index 1024v2Node v3, cut index 535v3Node v4, cut index 1020v4Node v5, cut index 611v5Node v6, cut index 1024v6Node v9, cut index 446v9Node v10, cut index 1020v10Node v13, cut index 1v13Node v14, cut index 1024v14Node v19, cut index 296v19Node v20, cut index 446v20Node v21, cut index 751v21Node v22, cut index 1020v22Node v29, cut index 404v29Node v30, cut index 1024v30Node v41, cut index 170v41Node v42, cut index 446v42Node v43, cut index 576v43Node v44, cut index 751v44Node v45, cut index 114v45Node v46, cut index 1020v46Node v87, cut index 550v87Node v88, cut index 576v88
One batch. Multiple MH transitions.Prompt 0 · Tree 1

Goal

Sample from the LLM’s power-sharpened distribution:

πα(x1:n|x0)∝p0(x1:n|x0)α,α>1

• p0 is the base model.
• x1:n is the continuation, and x0 is the prompt.
Raising sequence probabilities to α favors higher-likelihood continuations.

TL;DR: We present PreSTO, which preserves the same MH chain while running much faster.

PreSTO: execute several MH transitions per call

  1. Step 1. Collect feasible requests from a subtree of possible accept/reject outcomes, using prefixes that are already available.
  2. Step 2. Generate and score the proposals together in one batched model call.
  3. Step 3. Walk down the tree using MH acceptance rule
Loading animation…

PreSTO in Action

Recorded subtree

Rounded subtree · ε = 0.01Sampled pathOther prefetched nodes

Experiments

Main benchmark

Across 92 sampler–LLM–dataset settings, PreSTO (ours) speeds up PowerMH, EntropyCut, and MultiTryMH by a median of 1.71×, 1.88×, and 2.45×, respectively.

Case 1 · Model-call efficiency

At 100 transitions, cumulative time falls from 481.02 to 253.29 seconds. Calls do more work, but the reduction in their number outweighs their higher cost.

Cumulative model-call time

MH transitions per call

Time per model call

PreSTO-PowerMHPowerMHShading: ±1 SD

Qwen3.5-9B · LiveCodeBench · Prefetch budget 10 · BFS default Traversal

Case 2 · Our observation: the prefetched tree is sparse

Across seven datasets, approximately 67%–84% of edges are ε-certain in the prefetched trees (PreSTO-PowerMH, Qwen3.5-9B).

Predictive traversal vs. BFS

Predictive traversal raises mean speedup in all six settings, reaching 2.46×. The largest time reductions occur for EntropyCut at budgets 4–12; the smaller gains fall within one standard deviation of cumulative time.

Speedup over PowerMH

Higher is better

MH transitions per call

Higher is better

Cumulative model-call time

Seconds · mean ± SD

Predictive traversalBFS default Traversal

Qwen3.5-9B · LCB V6 · 100 MH transitions

Case 3 · Likelihood and confidence

Paired TOST establishes equivalence in 12 of 16 PowerMH tests and 17 of 18 EntropyCut tests. Both samplers are equivalent when pooled, within ±0.2 baseline standard deviations.

(a) PowerMH · Token log-likelihood

(b) PowerMH · Token confidence

(c) EntropyCut · Token log-likelihood

(d) EntropyCut · Token confidence

Base samplerPreSTO variantEquivalence established (TOST p < 0.05)

Boxes show per-prompt terminal-trace distributions under p₀ for eight PowerMH pairs and nine EntropyCut pairs, with prefetch budget 20. Shaded rows establish equivalence; paired TOST p-values appear at right.

Case 4 · Effect of prefetch budget

Speedup peaks at 1.94× with budget 16, using 5.01% of the preallocated KV pool. Larger budgets increase uncached work without a consistent speedup gain.

Sequential PowerMH and PreSTO at five prefetch budgets
MetricPowerMHPreSTO · Prefetch budget
48121620

Qwen3.5-9B · LiveCodeBench · BFS default Traversal · One seed per budget

BibTeX

@misc{jiang2026presto,
  title  = {{PreSTO}: Predictive Subtree Prefetching for Fast {LLM} Power Sampling},
  author = {Jiang, Nan and Theodoropoulos, Panagiotis and Deng, Wei},
  year   = {2026}
}