PreSTO：用于快速大语言模型幂采样的预测性子树预取

# PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling
Source: [https://arxiv.org/html/2610.13171](https://arxiv.org/html/2610.13171)
\\reportnumber

Panagiotis TheodoropoulosAffiliation:Georgia Institute of TechnologyWei DengCorresponding author:njiang@utep\.eduAffiliation:Morgan Stanley

###### 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 aprefetched subtreeof 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 apredictive traversal rulethat chooses the subtree to maximize the predicted number of completed transitions\. Across seven datasets and five base LLMs, PreSTO achieves median speedups of1\.71×1\.71\\times,1\.91×1\.91\\times, and2\.33×2\.33\\timeson PowerMH and its follow\-ups EntropyCut and MultiTryMH, respectively; on the first two, it makes a median of3\.9×3\.9\\timesfewer model calls, each only2\.1×2\.1\\timeslonger\. On LCB V6 with Qwen3\.5\-9B, the predictive traversal rule is a further1\.25×1\.25\\times–1\.37×1\.37\\timesfaster than the default breadth\-first traversal\.Code:[https://github\.com/nan\-jiang\-group/PreSTO](https://github.com/nan-jiang-group/PreSTO) Project Page:[https://nan\-jiang\-group\.github\.io/PreSTO](https://nan-jiang-group.github.io/PreSTO)

## 1Introduction

Figure 1:Across 105 sampler–LLM–dataset settings, PreSTO \(ours\) speeds up PowerMH, EntropyCut, and MultiTryMH by a median of1\.71×1\.71\\times,1\.91×1\.91\\times, and2\.33×2\.33\\times, respectively\. Each point is one setting, and faster settings lie toward the upper right\.Large language models \(LLMs\) perform strongly on reasoning tasks such as competition mathematics, code generation, and graduate\-level science questions\([Hendrycks et al\., 2021b](https://arxiv.org/html/2610.13171#bib.bib24);[Li et al\., 2022](https://arxiv.org/html/2610.13171#bib.bib35);[Rein et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib45)\)\. These capabilities are commonly improved by reinforcement learning \(RL\) post\-training with task\-specific rewards\([Guo et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib18);[Hu et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib25)\)\. Recent work suggests that RL post\-training largely sharpens the base model’s distribution\([He et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib21);[Shao et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib49);[Chen et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib11)\), and that sampling directly from a sharpened distribution, known as*power sampling*, can perform comparably to RL post\-training without additional training\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)\.

However, PowerMH, the Metropolis–Hastings \(MH\) sampler for power sampling, is expensive\([Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27)\): on MATH500, it generates up to8\.8×8\.8\\timesas many tokens as standard sampling\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\), and on LCB V6 with Qwen3\.5\-9B, it takes6\.5×6\.5\\times–18\.4×18\.4\\timesas long per prompt as single\-sample low\-temperature sampling \(Case Study 8, Appendix[E\.8](https://arxiv.org/html/2610.13171#A5.SS8)\)\. Follow\-up work improves it in four directions: \(1\)*Alternative samplers*replace serial MH with sequential Monte Carlo \(SMC\) or replica exchange\([Azizi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib5);[He et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib22)\)\. \(2\)*Efficient approximations*of the power target reduce inference cost\([Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27);[Nguyen et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib44)\)\. \(3\)*Proposal refinements*choose cut indices by token\-level entropy to improve mixing\([Zhou et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib62);[Guo et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib19)\)\. \(4\)*Objective or training changes*target the answer marginal\([Arzhantsev et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib3)\)or fine\-tune the model on power\-sampled responses\([Tomihari and Sato, 2026](https://arxiv.org/html/2610.13171#bib.bib55)\)\.

The main bottleneck of PowerMH is the sequential dependence between MH transitions: in a standard implementation, each proposal must be accepted or rejected before the next is generated from the resulting state\. We draw on prefetching in classical MCMC\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6);[Angelino et al\., 2014](https://arxiv.org/html/2610.13171#bib.bib2)\): future MH transitions form a tree of accept/reject outcomes, and each sequential run traces one root\-to\-leaf path\. If the proposals on this path are available in advance, several transitions complete without another model call\.

We present Predictive SubTree Prefetching \(PreSTO\),a framework for accelerating MH\-based sharpened sampling by completing several MH transitions per model call\. In each round, PreSTO builds a*prefetched subtree*, generates its feasible proposals in one batched model call, and follows the realized path with the original MH acceptance rule\. We prove that PreSTO\-PowerMH leaves the MH transition kernel of PowerMH unchanged \(Proposition[1](https://arxiv.org/html/2610.13171#Thmproposition1)\)\. We further observe that, under the power\-sharpened target, MH reaches only a sparse, nearly unary part of each prefetched subtree \(Figure[4](https://arxiv.org/html/2610.13171#S3.F4)and Appendix[E\.4](https://arxiv.org/html/2610.13171#A5.SS4)\), so a breadth\-first traversal spends much of the budget on nodes that MH rarely visits\. Motivated by this, we propose a improved*predictive traversal rule*that allocates the prefetch budget to maximize the expected number of MH transitions completed per call\. PreSTO trades fewer serial calls for a costlier batched call; with prefix\-cache reuse across requests, total latency falls whenever the saved calls outweigh the extra cost per batch\.

In experiments, we apply PreSTO to PowerMH, EntropyCut, and MultiTryMH on seven datasets and five base LLMs\. PreSTO is never slower than its baseline in all 105 settings, with median speedups of1\.71×1\.71\\timesover PowerMH,1\.91×1\.91\\timesover EntropyCut, and2\.33×2\.33\\timesover MultiTryMH, and maximum speedups of2\.29×2\.29\\timesand2\.85×2\.85\\timesover the first two \(Figure[1](https://arxiv.org/html/2610.13171#S1.F1)\)\. Our case studies show that\(1\)the speedup comes from fewer model calls rather than cheaper ones: over PowerMH, PreSTO\-PowerMH makes1\.94×1\.94\\times–4\.92×4\.92\\timesfewer calls, each taking1\.90×1\.90\\times–3\.42×3\.42\\timesas long \(Figure[1](https://arxiv.org/html/2610.13171#S1.F1)\);\(2\)the log\-likelihood and confidence of PreSTO outputs pass paired equivalence tests against the baselines in 29 of 38 comparisons, which supports that PreSTO leaves the MH transition kernel unchanged \(Figure[6](https://arxiv.org/html/2610.13171#S5.F6)\); and\(3\)the predictive traversal rule is1\.25×1\.25\\times–1\.37×1\.37\\timesfaster than the default breadth\-first search \(BFS\) traversal at all five prefetch budgets tested on LCB V6 with Qwen3\.5\-9B \(Figure[7](https://arxiv.org/html/2610.13171#S5.F7)\)\.

## 2Preliminaries

Metropolis–Hastings \(MH\)is an MCMC algorithm for sampling from a distribution known only up to a normalizing constant\([Metropolis et al\., 1953](https://arxiv.org/html/2610.13171#bib.bib39);[Hastings, 1970](https://arxiv.org/html/2610.13171#bib.bib20)\)\. MH constructs a Markov chain𝐱\(0\)→⋯→𝐱\(k\)→⋯→𝐱\(K\)\\mathbf\{x\}^\{\(0\)\}\\to\\cdots\\to\\mathbf\{x\}^\{\(k\)\}\\to\\cdots\\to\\mathbf\{x\}^\{\(K\)\}to sample from a target distributionπ⁡\(𝐱\)\\pi\(\\mathbf\{x\}\)\. Given the current state𝐱\(k\)\\mathbf\{x\}^\{\(k\)\}, a candidate𝐲\\mathbf\{y\}is drawn from a proposal distributionq\(⋅∣𝐱\(k\)\)q\(\\cdot\\mid\\mathbf\{x\}^\{\(k\)\}\)and is accepted with probability

A⁡\(𝐲,𝐱\(k\)\)=min⁡\{1,π⁡\(𝐲\)​q​\(𝐱\(k\)∣𝐲\)π⁡\(𝐱\(k\)\)​q​\(𝐲∣𝐱\(k\)\)\}\.A\(\\mathbf\{y\},\\mathbf\{x\}^\{\(k\)\}\)=\\min\\\!\\left\\\{1,\\frac\{\\pi\(\\mathbf\{y\}\)\\,q\(\\mathbf\{x\}^\{\(k\)\}\\mid\\mathbf\{y\}\)\}\{\\pi\(\\mathbf\{x\}^\{\(k\)\}\)\\,q\(\\mathbf\{y\}\\mid\\mathbf\{x\}^\{\(k\)\}\)\}\\right\\\}\.\(1\)If the proposal is accepted, the chain moves to𝐱\(k\+1\)←𝐲\\mathbf\{x\}^\{\(k\+1\)\}\\leftarrow\\mathbf\{y\}; otherwise,𝐱\(k\+1\)←𝐱\(k\)\\mathbf\{x\}^\{\(k\+1\)\}\\leftarrow\\mathbf\{x\}^\{\(k\)\}\.

Power Sharpening for LLMs\.Let𝐱0\\mathbf\{x\}\_\{0\}denote a given prompt and𝐱0:n=\(𝐱0,x1,…,xn\)\\mathbf\{x\}\_\{0:n\}=\(\\mathbf\{x\}\_\{0\},x\_\{1\},\\dots,x\_\{n\}\)denote the prompt followed bynngenerated tokens\. Letp0p\_\{0\}denote the distribution of the base LLM\. Recently,[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28)proposed to sample from a*power\-sharpened*distribution:

πα\(𝐱1:n∣𝐱0\)∝p0\(𝐱1:n∣𝐱0\)α\.\\displaystyle\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:n\}\\mid\\mathbf\{x\}\_\{0\}\)\\;\\propto\\;p\_\{0\}\(\\mathbf\{x\}\_\{1:n\}\\mid\\mathbf\{x\}\_\{0\}\)^\{\\alpha\}\.\(2\)Whenα\>1\\alpha\>1, the exponent sharpens the base distribution to amplify high\-likelihood continuations and suppress low\-likelihood ones\([Li et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib32)\)\. Empirical results\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28);[Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27)\)show that power sharpening can achieve performance competitive with RL\-based post\-training methods, such as Group Relative Policy Optimization \(GRPO\)\([Shao et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib50)\)\.

Exact sampling fromπα\\pi\_\{\\alpha\}in \([2](https://arxiv.org/html/2610.13171#S2.E2)\) is intractable, as it requires summing over future continuations\.[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28)propose PowerMH, an MH\-based sampler that proceeds through a sequence of intermediate targets block by block:

πα\(𝐱1:B∣𝐱0\)→⋯→πα\(𝐱1:ℓ​B∣𝐱0\)→⋯→πα\(𝐱1:n∣𝐱0\),\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:B\}\\mid\\mathbf\{x\}\_\{0\}\)\\rightarrow\\cdots\\rightarrow\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:\\ell B\}\\mid\\mathbf\{x\}\_\{0\}\)\\rightarrow\\cdots\\rightarrow\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:n\}\\mid\\mathbf\{x\}\_\{0\}\),\(3\)whereBBis the block size and the stage\-ℓ\\elltarget raises the base model’s distribution over the firstℓ​B\\ell Bgenerated tokens to the powerα\\alpha,

πα\(𝐱1:ℓ​B∣𝐱0\)∝p0\(𝐱1:ℓ​B∣𝐱0\)α,\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:\\ell B\}\\mid\\mathbf\{x\}\_\{0\}\)\\;\\propto\\;p\_\{0\}\(\\mathbf\{x\}\_\{1:\\ell B\}\\mid\\mathbf\{x\}\_\{0\}\)^\{\\alpha\},\(4\)which equals \([2](https://arxiv.org/html/2610.13171#S2.E2)\) at the last stage,ℓ​B=n\\ell B=n\. At theℓ\\ell\-th stage, PowerMH runs MH steps targeting the distributionπα\(𝐱1:ℓ​B∣𝐱0\)\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:\\ell B\}\\mid\\mathbf\{x\}\_\{0\}\)by first extending the sample𝐱0:\(ℓ−1\)​B\\mathbf\{x\}\_\{0:\(\\ell\-1\)B\}from the previous stage by one block to produce𝐱1:ℓ​B\\mathbf\{x\}\_\{1:\\ell B\}, and then refining it withKKMH steps\.

## 3Methodology

Figure 2:Our subtree prefetching \(PreSTO\) accelerates PowerMH for transitions𝐱→𝐲→𝐲\\mathbf\{x\}\\to\\mathbf\{y\}\\to\\mathbf\{y\}\.\(a\)PowerMH performs two sequential rounds of proposal generation withqτq\_\{\\tau\}followed by an MH accept/reject decision\.\(b\)Our method collects feasible requests by traversing the prefetching tree, generates proposals\(𝐲,𝐳\)\(\\mathbf\{y\},\\mathbf\{z\}\)in one batched call, and then samples a path over the subtree\.### 3\.1Motivation

Prior studies\([Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27);[Azizi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib5)\)show that PowerMH incurs substantial inference\-time latency\. On the MATH500 dataset,[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28)report that PowerMH generates up to8\.8×8\.8\\timesas many tokens as standard sampling\. In our measurements on LCB V6 with Qwen3\.5\-9B \(Case Study 8, Appendix[E\.8](https://arxiv.org/html/2610.13171#A5.SS8)\), PowerMH withK=10K=10,2020, and3030MH steps takes6\.5×6\.5\\times,12\.2×12\.2\\times, and18\.4×18\.4\\timesas long per prompt as low\-temperature sampling, which draws a single sample\. This latency arises from theinherently sequential nature of MH: the proposal at stepk\+1k\{\+\}1can be generated only after the accept/reject outcome at stepkkdetermines the next state\.

We first describe the suffix\-resampling procedure in the PowerMH sampler\. For notational clarity, letL=\(ℓ−1\)​BL=\(\\ell\-1\)BandT=ℓ​BT=\\ell Bbe the sequence lengths before and after theℓ\\ell\-th stage\. Given the sequence𝐱0:L\\mathbf\{x\}\_\{0:L\}from the previous stage, the sampler first extends it to𝐱0:T\\mathbf\{x\}\_\{0:T\}by sampling a continuation from the proposal LLM, and this extended sequence is the initial MH state𝐱\(0\)=𝐱0:T\\mathbf\{x\}^\{\(0\)\}=\\mathbf\{x\}\_\{0:T\}\. At stepkkwith MH state𝐱\(k\)\\mathbf\{x\}^\{\(k\)\}, the sampler draws a cut indexc∼Unif​\{0,…,T−1\}c\\sim\\mathrm\{Unif\}\\\{0,\\ldots,T\-1\\\}, and resamples the suffix from the proposal LLM to construct a candidate𝐲=\(𝐱0:c\(k\),𝐲c\+1:T\)\\mathbf\{y\}=\\bigl\(\\mathbf\{x\}^\{\(k\)\}\_\{0:c\},\\mathbf\{y\}\_\{c\+1:T\}\\bigr\):

yt∼qτ\(⋅∣𝐱\(k\)0:c,𝐲c\+1:t−1\),\\displaystyle y\_\{t\}\\sim q\_\{\\tau\}\\\!\\left\(\\cdot\\mid\\mathbf\{x\}^\{\(k\)\}\_\{0:c\},\\mathbf\{y\}\_\{c\+1:t\-1\}\\right\),for​t=c\+1,…,T,\\displaystyle\\text\{ for \}t=c\+1,\\ldots,T,\(5\)where the proposal distributionqτq\_\{\\tau\}is the base LLM with temperatureτ\\tau\. The next state𝐱\(k\+1\)\\mathbf\{x\}^\{\(k\+1\)\}is then determined by applying the acceptance rule in \([1](https://arxiv.org/html/2610.13171#S2.E1)\) to the candidate𝐲\\mathbf\{y\}\.

MCMC Prefetchingis a form of*speculative computation*in MCMC that accelerates an inherently sequential process by precomputing multiple possible future MH transitions before the corresponding accept/reject decisions are realized\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6);[Angelino et al\., 2014](https://arxiv.org/html/2610.13171#bib.bib2);[Ye and Lu, 2024](https://arxiv.org/html/2610.13171#bib.bib58)\)\. In our setting, prefetching is best understood through a depth\-KKtree, which enumerates all possible accept/reject outcomes over the nextKKMH steps\. Each tree nodeviv\_\{i\}is associated with a cut indexcic\_\{i\}and a proposed candidate\. Its left branch corresponds to accepting a newly proposed candidate, whereas its right branch corresponds to a rejection decision\. Every realization ofKKMH transitions corresponds to a root\-to\-leaf path in the tree\. Example[1](https://arxiv.org/html/2610.13171#Thmexample1)explains this construction in detail\.

###### Example 1\.

Figure[2](https://arxiv.org/html/2610.13171#S3.F2)\(a\) shows the two\-step PowerMH trajectory𝐱→𝐲→𝐲\\mathbf\{x\}\\to\\mathbf\{y\}\\to\\mathbf\{y\}\. In round 1, starting at𝐱\\mathbf\{x\}, the sampler draws cut indexc1c\_\{1\}, resamples the suffix according to \([5](https://arxiv.org/html/2610.13171#S3.E5)\) to generate𝐲\\mathbf\{y\}, and accepts the proposal, yielding𝐱\(1\)=𝐲\\mathbf\{x\}^\{\(1\)\}=\\mathbf\{y\}\. In round 2, it draws a new cut indexc2c\_\{2\}and resamples the suffix of𝐲\\mathbf\{y\}to generate𝐳\\mathbf\{z\}, but rejects this proposal, leaving𝐱\(2\)=𝐲\\mathbf\{x\}^\{\(2\)\}=\\mathbf\{y\}\. These accept/reject decisions select the path𝐱→𝐲→𝐲\\mathbf\{x\}\\to\\mathbf\{y\}\\to\\mathbf\{y\}in the prefetched subtree in step 3 of Figure[2](https://arxiv.org/html/2610.13171#S3.F2)\(b\)\.

To accelerate PowerMH and its follow\-up variants, we propose to construct aprefetched subtreethat represents multiple possible future MH states and then select one root\-to\-leaf path using \([1](https://arxiv.org/html/2610.13171#S2.E1)\)\.

### 3\.2Subtree Prefetching for MH\-Based Power Sharpening

Our method is composed of \(1\) collecting feasible suffix\-resampling requests from the subtree, \(2\) sampling proposal sequences and computing acceptance probabilities, and \(3\) performing MH transitions over the prefetched subtree by moving to the left or right child recursively\.

\(1\) Collecting feasible requests\.We use breadth\-first search \(BFS\) to traverse the prefetching tree and collect at mostNpfN\_\{\\mathrm\{pf\}\}feasible suffix\-resampling requests\. In the BFS construction, we initialize a queue at the subtree root and traverse nodes in breadth\-first order\. Each request is a tuple\(vi,ci\)\(v\_\{i\},c\_\{i\}\), whereviv\_\{i\}identifies the node andcic\_\{i\}denotes its cut index\. Expanding a node creates two children: an acceptance \(left\) child and a rejection \(right\) child\. For each acceptance childviv\_\{i\}, we draw a new cut indexci∼Unif⁡\{0,…,T−1\}c\_\{i\}\\sim\\mathrm\{Unif\}\\\{0,\\ldots,T\-1\\\}and form the request\(vi,ci\)\(v\_\{i\},c\_\{i\}\)\. If this request satisfies Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), we add it to the batch and enqueueviv\_\{i\}for further expansion\. Otherwise, we defer the request while retaining its original cut index; if its branch is reached, we evaluate it in a later batch\. We enqueue the rejection child but do not add a corresponding request to the batch, because the child retains its parent’s state and therefore requires no new proposal\. Our BFS implementation enqueues the rejection child even when the node’s own request is deferred\. The requests that BFS then places below this child are generated and scored, but the MH walk of this batch stops at the deferred node and never reaches them; atNpf=10N\_\{\\mathrm\{pf\}\}=10on LCB V6 with Qwen3\.5\-9B, they are19%19\\%of the issued requests \(Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)\)\. The traversal stops when the batch containsNpfN\_\{\\mathrm\{pf\}\}requests or the queue is empty\. Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3)introduces our predictive traversal rule, which improves on the default BFS traversal by maximizing a predicted expected\-transition objective, informed by an empirical property of prefetching trees observed across all datasets in Figure[4](https://arxiv.org/html/2610.13171#S3.F4)\.

###### Condition 1\.

Letvvbe a node in the prefetching tree with cut indexccandv′v^\{\\prime\}be its acceptance child with cut indexc′c^\{\\prime\}\. The request associated withv′v^\{\\prime\}is feasible for the current prefetch batch ifc′≤cc^\{\\prime\}\\leq c\.

Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)follows from the suffix\-resampling step in \([5](https://arxiv.org/html/2610.13171#S3.E5)\)\. Fix a state𝐱=𝐱0:T\\mathbf\{x\}=\\mathbf\{x\}\_\{0:T\}and a cut0≤c≤T−10\\leq c\\leq T\-1, and let𝐲=\(𝐱0:c,𝐲c\+1:T\)\\mathbf\{y\}=\(\\mathbf\{x\}\_\{0:c\},\\mathbf\{y\}\_\{c\+1:T\}\)be a candidate obtained by suffix resampling atcc\. For any0≤c′≤c0\\leq c^\{\\prime\}\\leq c, the preserved prefix satisfies𝐲0:c′=𝐱0:c′\\mathbf\{y\}\_\{0:c^\{\\prime\}\}=\\mathbf\{x\}\_\{0:c^\{\\prime\}\}\. Hence, for every suffix𝐳c′\+1:T\\mathbf\{z\}\_\{c^\{\\prime\}\+1:T\}, autoregressive factorization gives

qτ\(𝐳c′\+1:T\|𝐲0:c′\)=∏t=c′\+1Tqτ\(zt\|𝐲0:c′,𝐳c′\+1:t−1\)=∏t=c′\+1Tqτ\(zt\|𝐱0:c′,𝐳c′\+1:t−1\)=qτ\(𝐳c′\+1:T\|𝐱0:c′\)\.q\_\{\\tau\}\(\\mathbf\{z\}\_\{c^\{\\prime\}\+1:T\}\|\\mathbf\{y\}\_\{0:c^\{\\prime\}\}\)=\\prod\_\{t=c^\{\\prime\}\+1\}^\{T\}q\_\{\\tau\}\(z\_\{t\}\|\\mathbf\{y\}\_\{0:c^\{\\prime\}\},\\mathbf\{z\}\_\{c^\{\\prime\}\+1:t\-1\}\)=\\prod\_\{t=c^\{\\prime\}\+1\}^\{T\}q\_\{\\tau\}\(z\_\{t\}\|\\mathbf\{x\}\_\{0:c^\{\\prime\}\},\\mathbf\{z\}\_\{c^\{\\prime\}\+1:t\-1\}\)=q\_\{\\tau\}\(\\mathbf\{z\}\_\{c^\{\\prime\}\+1:T\}\|\\mathbf\{x\}\_\{0:c^\{\\prime\}\}\)\.Consequently, the proposal at cutc′c^\{\\prime\}can be generated in the same batch from the already available prefix𝐱0:c′\\mathbf\{x\}\_\{0:c^\{\\prime\}\}, before𝐲\\mathbf\{y\}is available, without changing its conditional distribution\. Example[2](https://arxiv.org/html/2610.13171#Thmexample2)visualizes how BFS collects suffix\-resampling requests and checks Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)\.

###### Example 2\.

To collect a batch ofNpf=2N\_\{\\mathrm\{pf\}\}=2requests from the tree in step 1 of Figure[2](https://arxiv.org/html/2610.13171#S3.F2)\(b\), we start BFS at the root nodev0v\_\{0\}, which represents the current sequence𝐱0:T\\mathbf\{x\}\_\{0:T\}\. We assign it the cut indexc0=Tc\_\{0\}=Tfor consistency with Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)\. We expand the tree in the orderv0,v1,v2,…v\_\{0\},v\_\{1\},v\_\{2\},\\ldots\. Whenever we visit an acceptance \(left\) child, we independently sample a new cut index for it\. If each sampled cut index satisfies Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), we add the request\(v1,c1\)\(v\_\{1\},c\_\{1\}\), followed by the request\(v3,c2\)\(v\_\{3\},c\_\{2\}\)\.

As shown in step 2 of Figure[2](https://arxiv.org/html/2610.13171#S3.F2)\(b\), resampling the suffix atv1v\_\{1\}after cut indexc1c\_\{1\}leaves the prefix𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}unchanged becausec2≤c1c\_\{2\}\\leq c\_\{1\}\. Then, the proposal atv3v\_\{3\}is conditioned only on theshared prefix𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}, which is already available at the root nodev0v\_\{0\}\. The two suffix\-resampling requests\(v1,c1\)\(v\_\{1\},c\_\{1\}\)and\(v3,c2\)\(v\_\{3\},c\_\{2\}\)can therefore be issued in the same model call\.

\(2\) Batched proposal sampling\.The collected feasible suffix\-resampling requests are submitted in a single batched call to the serving engine of the proposal LLM \(e\.g\., vLLM\([Kwon et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib29)\)or SGLang\([Zheng et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib61)\)\), which returns the resampled suffixes together with their log\-probabilities\. These log\-probabilities are used to compute the MH log\-acceptance probability\. Because many requests share long prefixes, the KV cache for each shared prefix can be computed once and reused by all requests that extend it\. Modern LLM serving engines support this reuse through*prefix caching*\. The following Example[3](https://arxiv.org/html/2610.13171#Thmexample3)explains the detailed calculation procedure\. Example[4](https://arxiv.org/html/2610.13171#Thmexample4)\(Appendix[B\.3](https://arxiv.org/html/2610.13171#A2.SS3)\) visualizes how KV\-cache reuse reduces repeated prefix computation across batched requests\.

###### Example 3\.

In steps 2 and 3 of Figure[2](https://arxiv.org/html/2610.13171#S3.F2)\(b\), sequence𝐱\\mathbf\{x\}is associated with the rootv0v\_\{0\}, while𝐲\\mathbf\{y\}and𝐳\\mathbf\{z\}are the newly resampled sequences associated with nodesv1v\_\{1\}andv3v\_\{3\}, respectively, in the tree shown in step 3\. For the request\(v1,c1\)\(v\_\{1\},c\_\{1\}\),𝐲\\mathbf\{y\}is obtained by resampling the suffix from the proposal LLMqτq\_\{\\tau\}conditioned on the prefix𝐱0:c1\\mathbf\{x\}\_\{0:c\_\{1\}\}\. Thus,𝐲=\(𝐱0:c1,𝐲c1\+1:T\)\\mathbf\{y\}=\\bigl\(\\mathbf\{x\}\_\{0:c\_\{1\}\},\\mathbf\{y\}\_\{c\_\{1\}\+1:T\}\\bigr\)\. By \([1](https://arxiv.org/html/2610.13171#S2.E1)\), the log\-acceptance probability for the MH transition from𝐱\\mathbf\{x\}to𝐲\\mathbf\{y\}is

logA\(𝐲,𝐱\)=min\{0,\\displaystyle\\log A\(\\mathbf\{y\},\\mathbf\{x\}\)=\\min\\\{0,logqτ\(𝐱c1\+1:T∣𝐱0:c1\)−logqτ\(𝐲c1\+1:T∣𝐱0:c1\)\\displaystyle\\log q\_\{\\tau\}\(\\mathbf\{x\}\_\{c\_\{1\}\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\}\)\-\\log q\_\{\\tau\}\(\\mathbf\{y\}\_\{c\_\{1\}\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\}\)\(6\)\+α\(logp0\(𝐲c1\+1:T∣𝐱0:c1\)−logp0\(𝐱c1\+1:T∣𝐱0:c1\)\)\}\.\\displaystyle\+\\alpha\\left\(\\log p\_\{0\}\(\\mathbf\{y\}\_\{c\_\{1\}\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\}\)\-\\log p\_\{0\}\(\\mathbf\{x\}\_\{c\_\{1\}\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\}\)\\right\)\\\}\.The calculations are performed in the log domain for numerical stability\. Each sequence\-level term is computed by summing token\-level log\-probabilities, such aslogqτ\(𝐲c1\+1:T∣𝐱0:c1\)=∑t=c1\+1Tlogqτ\(yt∣𝐱0:c1,𝐲c1\+1:t−1\)\\log q\_\{\\tau\}\(\\mathbf\{y\}\_\{c\_\{1\}\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\}\)=\\sum\_\{t=c\_\{1\}\+1\}^\{T\}\\log q\_\{\\tau\}\(y\_\{t\}\\mid\\mathbf\{x\}\_\{0:c\_\{1\}\},\\mathbf\{y\}\_\{c\_\{1\}\+1:t\-1\}\)\. Appendix[B\.1](https://arxiv.org/html/2610.13171#A2.SS1)provides the derivation of \([6](https://arxiv.org/html/2610.13171#S3.E6)\)\.

\(3\) MH transitions over the prefetched subtree\.Starting from the subtree root, representing the current MH state, we simulate the MH accept/reject decisions sequentially along a single root\-to\-leaf path\. At each nodevv, we follow the left edge with probabilityA⁡\(v\+,v\)A\(v^\{\+\},v\)and the right edge otherwise\. The resulting root\-to\-leaf path determines a sequence of accept/reject decisions and, consequently, the final MH state\. We update the current state to the sequence associated with the realized leaf and retain its token\-level log\-probabilities under the proposal LLMqτq\_\{\\tau\}and the base modelp0p\_\{0\}for computing MH acceptance probabilities\. Example[5](https://arxiv.org/html/2610.13171#Thmexample5)\(Appendix[B\.3](https://arxiv.org/html/2610.13171#A2.SS3)\) visualizes the above process with the calculated acceptance probabilities from \([6](https://arxiv.org/html/2610.13171#S3.E6)\)\.

Algorithms[3\.2](https://arxiv.org/html/2610.13171#S3.SS2)and[3\.2](https://arxiv.org/html/2610.13171#S3.SS2)place the original PowerMH sampler and PreSTO\-PowerMH side by side\. Both share the same blockwise outer loop and the same acceptance rule; they differ only in how theKKMH steps of a block are executed\. PowerMH issues one model call per MH step and must wait for each accept/reject outcome before forming the next proposal\. PreSTO\-PowerMH instead issues one*batched*call per prefetch round and realizeskΔ≥1k\_\{\\Delta\}\\geq 1MH steps from it\. In Algorithm[3\.2](https://arxiv.org/html/2610.13171#S3.SS2),PrefetchAndScorebuilds the prefetching tree rooted at the current state𝐱\\mathbf\{x\}, collects at mostNpfN\_\{\\mathrm\{pf\}\}feasible requests under the tree traversal rule, and generates and scores them in one batched call\. It returns the scored prefetched subtree𝒯\\mathcal\{T\}; deferred requests keep their cut indices across rounds\.MHTransitionthen follows the realized accept/reject path through𝒯\\mathcal\{T\}for at mostK−kK\-ktransitions, the number that remain in the block, and returns the reached state𝐱Δ\\mathbf\{x\}\_\{\\Delta\}together with the numberkΔ≤K−kk\_\{\\Delta\}\\leq K\-kof completed transitions;PrefetchAndScorelikewise caps the tree at depthK−kK\-k\(Appendix[C\.1](https://arxiv.org/html/2610.13171#A3.SS1)\), so the block never exceedsKKtransitions\. Proposition[1](https://arxiv.org/html/2610.13171#Thmproposition1)further establishes that PreSTO\-PowerMH preserves the original MH transition kernel\.

Algorithm 1PowerMH\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)

Algorithm 2PreSTO\-PowerMH \(ours\)

Common settings:the base\-model distributionp0p\_\{0\}, proposal\-LLM distributionqτq\_\{\\tau\}, power\-sharpening coefficientα\\alpha, response lengthnn, block sizeBB, and MCMC steps per blockKK\. PreSTO\-PowerMH\-only settings:tree traversal rule, prefetch budgetNpfN\_\{\\mathrm\{pf\}\}\.

Output:the final state𝐱=𝐱0:n\\mathbf\{x\}=\\mathbf\{x\}\_\{0:n\}afterKKMH steps per block, approximately distributed asπα\\pi\_\{\\alpha\}\.

1:for

ℓ←1,…,n/B\\ell\\leftarrow 1,\\ldots,n/Bdo

2:Extend

𝐱0:L\\mathbf\{x\}\_\{0:L\}to

𝐱0:T\\mathbf\{x\}\_\{0:T\}using

qτq\_\{\\tau\}\.

3:for

k←1,…,Kk\\leftarrow 1,\\ldots,Kdo

4:

𝐲←DrawOneCandidate​\(𝐱\)\\mathbf\{y\}\\leftarrow\\textsc\{DrawOneCandidate\}\(\\mathbf\{x\}\)\.

5:

A←ComputeAcceptance​\(𝐲,𝐱\)A\\leftarrow\\textsc\{ComputeAcceptance\}\(\\mathbf\{y\},\\mathbf\{x\}\)\.

6:

u∼Unif⁡\(0,1\)u\\sim\\mathrm\{Unif\}\(0,1\)\.

7:if

u≤Au\\leq Athen

𝐱←𝐲\\mathbf\{x\}\\leftarrow\\mathbf\{y\}\.

1:for

ℓ←1,…,n/B\\ell\\leftarrow 1,\\ldots,n/Bdo

2:Extend

𝐱0:L\\mathbf\{x\}\_\{0:L\}to

𝐱0:T\\mathbf\{x\}\_\{0:T\}using

qτq\_\{\\tau\}\.

5:

𝒯←PrefetchAndScore​\(𝐱,Npf,K−k\)\\mathcal\{T\}\\leftarrow\\textsc\{PrefetchAndScore\}\(\\mathbf\{x\},N\_\{\\mathrm\{pf\}\},K\-k\)\.

6:

\(𝐱Δ,kΔ\)←MHTransition​\(𝒯,𝐱,K−k\)\(\\mathbf\{x\}\_\{\\Delta\},k\_\{\\Delta\}\)\\leftarrow\\textsc\{MHTransition\}\(\\mathcal\{T\},\\mathbf\{x\},K\-k\)\.

7:

k←k\+kΔk\\leftarrow k\+k\_\{\\Delta\};

𝐱←𝐱Δ\\mathbf\{x\}\\leftarrow\\mathbf\{x\}\_\{\\Delta\}\.

### 3\.3Predictive Subtree Allocation for Efficient Prefetching

Prefetching efficiency depends on the total workload to generate a batch and on the number of MH transitions that the batch completes\. We show that MH reaches only a sparse, nearly unary part of the prefetched tree, and use this observation to decide which subtree to prefetch under a budget\.

ϵ\\epsilon\-uncertainϵ\\epsilon\-certain rejectϵ\\epsilon\-certainacceptFigure 3:Theϵ\\epsilon\-rounded subtree \(orange\) is sparse and mostly has one child per node within the full prefetched subtree\. Blue edges trace a sampled MH path\.Our Observation\.Fixϵ∈\(0,12\)\\epsilon\\in\(0,\\tfrac\{1\}\{2\}\)\(we useϵ=0\.01\\epsilon=0\.01\), and letvvbe an expanded node with acceptance childv\+v^\{\+\}and rejection childv−v^\{\-\}, reached with probabilitiesA⁡\(v\+,v\)A\(v^\{\+\},v\)and1−A⁡\(v\+,v\)1\-A\(v^\{\+\},v\), respectively\. The decision atvvis anϵ\\epsilon\-certain accept ifA⁡\(v\+,v\)≥1−ϵA\(v^\{\+\},v\)\\geq 1\-\\epsilon, anϵ\\epsilon\-certain reject ifA⁡\(v\+,v\)≤ϵA\(v^\{\+\},v\)\\leq\\epsilon, andϵ\\epsilon\-uncertain otherwise \(see Figure[3](https://arxiv.org/html/2610.13171#S3.F3)for an example\)\. Rounding the acceptance probability of everyϵ\\epsilon\-certain decision to11or00leaves it with a single reachable child, whereas anϵ\\epsilon\-uncertain decision keeps both\. We call the nodes that remain reachable from the root after this rounding theϵ\\epsilon\-rounded subtree\.

Figure[7](https://arxiv.org/html/2610.13171#S5.F7)\(d\) and Appendix[E\.9](https://arxiv.org/html/2610.13171#A5.SS9)show prefetched subtrees in full, with theirϵ\\epsilon\-rounded subtrees in orange and the sampled paths in blue\. Most nodes lie outside theϵ\\epsilon\-rounded subtree, so MH is unlikely to visit them\. The default BFS traversal, however, expands decisions regardless of how likely MH is to reach them, and therefore spends much of the budget on nodes that MH rarely visits\.

Figure 4:Most edges in prefetched subtrees areϵ\\epsilon\-certain\.For PreSTO\-PowerMH with Qwen3\.5\-9B and the default BFS traversal,67%67\\%–95%95\\%of edges areϵ\\epsilon\-certain across all seven datasets, withϵ=0\.01\\epsilon=0\.01andNpf=20N\_\{\\mathrm\{pf\}\}=20\.Theϵ\\epsilon\-rounded subtree is predominantly unary because the target distributionπα\\pi\_\{\\alpha\}in \([2](https://arxiv.org/html/2610.13171#S2.E2)\) amplifies high\-likelihood continuations and suppresses low\-likelihood ones, which pushes most acceptance probabilities toward00or11\. Figure[4](https://arxiv.org/html/2610.13171#S3.F4)confirms that most edges areϵ\\epsilon\-certain atϵ=0\.01\\epsilon=0\.01: pooling the acceptance and rejection edges of all decisions, about95%95\\%of the edges areϵ\\epsilon\-certain on LCB V6 \(panel \(g\)\)\. Appendix[E\.4](https://arxiv.org/html/2610.13171#A5.SS4)reports additional acceptance distributions\.

Predictive traversal rule\.These observations motivate allocating prefetch requests selectively rather than uniformly\. We therefore design a traversal rule that, for the same budget, maximizes the predicted number of completed MH transitions\. Before generation, a three\-class logistic regression on the cut fractioncj/Tc\_\{j\}/Tof each candidate request predicts theϵ\\epsilon\-certainty class probabilities of the decision, and we convert them into a branch probability\. We then select at mostNpfN\_\{\\mathrm\{pf\}\}requests \(one per expanded node\) that maximize the predicted number of completed transitions \(Lemma[1](https://arxiv.org/html/2610.13171#Thmlemma1)\), computing this selection by dynamic programming over the acceptance and rejection subtrees \(Appendices[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)and[C\.4](https://arxiv.org/html/2610.13171#A3.SS4)\)\. We call this rule the*predictive traversal rule*, in contrast to the default BFS traversal of Section[3\.2](https://arxiv.org/html/2610.13171#S3.SS2)\. Case Study 5 in Section[5\.2](https://arxiv.org/html/2610.13171#S5.SS2)compares the two rules empirically, with extended results in Appendix[E\.5](https://arxiv.org/html/2610.13171#A5.SS5)\.

## 4Related Work

We review related work most relevant to PreSTO here; see Appendix[A](https://arxiv.org/html/2610.13171#A1)for an extended discussion\.

MCMC prefetching\.Like prior MCMC\-prefetching methods\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6);[Angelino et al\., 2014](https://arxiv.org/html/2610.13171#bib.bib2);[Ye and Lu, 2024](https://arxiv.org/html/2610.13171#bib.bib58)\), PreSTO precomputes candidates for future accept/reject outcomes before the realized path is known\. The methods differ in how they allocate this speculative work\.[Brockwell \(2006\)](https://arxiv.org/html/2610.13171#bib.bib6)and[Angelino et al\. \(2014\)](https://arxiv.org/html/2610.13171#bib.bib2)treat proposal generation as cheap and therefore prefetch many more candidates than the chain eventually uses\. LLM proposals are expensive, so PreSTO confines prefetching to a budgeted subtree\.[Ye and Lu \(2024\)](https://arxiv.org/html/2610.13171#bib.bib58)expand a regular multiproposal tree with a fixed number of proposals and a fixed prefetch depth, whereas PreSTO expands an irregular subtree: it uses Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)to identify feasible suffix requests and prioritizes them by predicted reach probability\.

Tree\-based speculative decoding \(TreeSD\)\([Miao et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib40);[Cai et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib7);[Li et al\., 2024b](https://arxiv.org/html/2610.13171#bib.bib34);[Li et al\., 2024a](https://arxiv.org/html/2610.13171#bib.bib33)\)also batches evaluations over a tree to reduce serial model calls, but its tree encodes different objects\. In TreeSD, branches are alternativedraft\-token continuations, and target\-model verification commits an accepted token prefix, as in single\-chain speculative decoding\([Stern et al\., 2018](https://arxiv.org/html/2610.13171#bib.bib51);[Leviathan et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib31);[Chen et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib9)\)\. In PreSTO, branches are the accept/reject outcomes ofcomplete\-sequence MH proposals, and following the realized MH decisions reproduces the sequential PowerMH trajectory\. The shared tree structure admits similar budget\-allocation arguments, but the unit of progress differs: each visited expanded node in PreSTO advances the chain by one MH transition, whether the proposal is accepted or rejected\.

Power\-sharpening methods\.Other work targets the power distribution through SMC\-based samplers\([Azizi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib5);[He et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib22)\), efficient approximations\([Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27);[Nguyen et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib44)\), refined proposals\([Zhou et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib62);[Guo et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib19)\), or modified objectives and training procedures\([Arzhantsev et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib3);[Tomihari and Sato, 2026](https://arxiv.org/html/2610.13171#bib.bib55)\)\. PreSTO takes a different route: it accelerates PowerMH itself, keeping its target, suffix proposal, and MH acceptance rule intact, and changes only the schedule by which proposals are generated and scored\.

## 5Experiments

We first show that PreSTO speeds up all three sequential samplers across base LLMs and datasets \(Table[1](https://arxiv.org/html/2610.13171#S5.T1)\)\. Five case studies \(Section[5\.2](https://arxiv.org/html/2610.13171#S5.SS2)\) then examine where the speedup comes from, how the prefetch budget affects it, whether the outputs are preserved, how often MH decisions areϵ\\epsilon\-certain, and how the traversal rule matters\. Appendix[D](https://arxiv.org/html/2610.13171#A4)describes the baselines, base LLMs, datasets, and metrics, and Appendix[E](https://arxiv.org/html/2610.13171#A5)reports the full results\.

Table 1:Speedup of PreSTO over sequential samplers: the mean cumulative model\-call time of the sampler divided by that of its PreSTO variant \([20](https://arxiv.org/html/2610.13171#A4.E20)\), on the first 20 prompts withK=100K=100andNpf=20N\_\{\\mathrm\{pf\}\}=20\.\(a\)PowerMH vs\. PreSTO\-PowerMHBase LLMMATH500AIME 24&25MBPPGPQAHumanEvalMMLULCB V6Qwen3\-4B2\.11×2\.11\\times2\.12×2\.12\\times1\.10×1\.10\\times1\.63×1\.63\\times1\.77×1\.77\\times1\.59×1\.59\\times2\.04×2\.04\\timesQwen3\-8B2\.23×2\.23\\times2\.29×2\.29\\times1\.00×1\.00\\times2\.12×2\.12\\times1\.81×1\.81\\times1\.50×1\.50\\times2\.05×2\.05\\timesQwen3\.5\-4B1\.49×1\.49\\times1\.66×1\.66\\times1\.67×1\.67\\times1\.69×1\.69\\times1\.59×1\.59\\times1\.76×1\.76\\times2\.02×2\.02\\timesQwen3\.5\-9B2\.06×2\.06\\times2\.08×2\.08\\times1\.61×1\.61\\times2\.05×2\.05\\times1\.21×1\.21\\times1\.18×1\.18\\times1\.44×1\.44\\timesGemma4\-12B\-it1\.74×1\.74\\times1\.76×1\.76\\times1\.44×1\.44\\times1\.67×1\.67\\times1\.71×1\.71\\times1\.52×1\.52\\times1\.95×1\.95\\times\(b\)EntropyCut vs\. PreSTO\-EntropyCutBase LLMMATH500AIME 24&25MBPPGPQAHumanEvalMMLULCB V6Qwen3\-4B1\.76×1\.76\\times1\.69×1\.69\\times1\.19×1\.19\\times2\.09×2\.09\\times1\.88×1\.88\\times2\.03×2\.03\\times1\.65×1\.65\\timesQwen3\-8B1\.75×1\.75\\times1\.80×1\.80\\times1\.43×1\.43\\times1\.79×1\.79\\times2\.05×2\.05\\times2\.20×2\.20\\times1\.54×1\.54\\timesQwen3\.5\-4B1\.57×1\.57\\times2\.06×2\.06\\times2\.46×2\.46\\times1\.96×1\.96\\times2\.06×2\.06\\times1\.65×1\.65\\times1\.70×1\.70\\timesQwen3\.5\-9B1\.76×1\.76\\times1\.76×1\.76\\times2\.85×2\.85\\times1\.96×1\.96\\times2\.85×2\.85\\times2\.38×2\.38\\times1\.91×1\.91\\timesGemma4\-12B\-it2\.27×2\.27\\times1\.52×1\.52\\times2\.10×2\.10\\times2\.16×2\.16\\times2\.32×2\.32\\times2\.35×2\.35\\times1\.79×1\.79\\times\(c\)MultiTryMH vs\. PreSTO\-MultiTryMHBase LLMMATH500AIME 24&25MBPPGPQAHumanEvalMMLULCB V6Qwen3\-4B2\.30×2\.30\\times2\.02×2\.02\\times2\.35×2\.35\\times2\.34×2\.34\\times2\.21×2\.21\\times2\.14×2\.14\\times2\.32×2\.32\\timesQwen3\-8B2\.08×2\.08\\times2\.02×2\.02\\times1\.97×1\.97\\times2\.05×2\.05\\times1\.91×1\.91\\times1\.92×1\.92\\times2\.08×2\.08\\timesQwen3\.5\-4B5\.80×5\.80\\times6\.12×6\.12\\times5\.35×5\.35\\times5\.64×5\.64\\times5\.59×5\.59\\times6\.36×6\.36\\times5\.76×5\.76\\timesQwen3\.5\-9B7\.01×7\.01\\times6\.90×6\.90\\times5\.93×5\.93\\times6\.83×6\.83\\times6\.18×6\.18\\times6\.92×6\.92\\times6\.87×6\.87\\timesGemma4\-12B\-it2\.27×2\.27\\times2\.54×2\.54\\times2\.18×2\.18\\times2\.13×2\.13\\times2\.17×2\.17\\times2\.33×2\.33\\times2\.22×2\.22\\times### 5\.1Acceleration Across Base LLMs and Datasets

We pair each sequential sampler \(PowerMH\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\), EntropyCut\([Zhou et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib62)\), and MultiTryMH\([Guo et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib19)\)\) with its PreSTO variant\. Both samplers in a pair runK=100K=100realized MH transitions on the first 20 prompts of each dataset and generate the full1,0241\{,\}024\-token response as a single block on the same vLLM backend, with the base LLM, power exponentα\\alpha, proposal rule, initialization, and prompts held fixed \(Appendix[D\.4](https://arxiv.org/html/2610.13171#A4.SS4)\)\.

Table[1](https://arxiv.org/html/2610.13171#S5.T1)reports the speedup for every base LLM–dataset pair \(full metrics in Appendix[E\.1](https://arxiv.org/html/2610.13171#A5.SS1)\)\. We find that\(1\)PreSTO speeds up all three baselines: it is never slower in the 105 settings, reaches at least1\.5×1\.5\\timesin 96, and achieves median speedups of1\.71×1\.71\\timesover PowerMH,1\.91×1\.91\\timesover EntropyCut, and2\.33×2\.33\\timesover MultiTryMH \(ranges1\.00×1\.00\\times–2\.29×2\.29\\times,1\.19×1\.19\\times–2\.85×2\.85\\times, and1\.91×1\.91\\times–7\.01×7\.01\\times, respectively\)\. Over MultiTryMH, part of the speedup comes from the implementation rather than from prefetching: sequential MultiTryMH rescores every candidate at all three temperatures, whereas PreSTO\-MultiTryMH reuses the sampled log\-probabilities \(Appendix[E\.1](https://arxiv.org/html/2610.13171#A5.SS1)\)\. Each PreSTO call completes several MH transitions, which cuts the number of model calls by1\.77×1\.77\\times–4\.92×4\.92\\times\.\(2\)The gain is largest when the sequential step is expensive: on MBPP with Qwen3\.5\-9B, an EntropyCut step \(7\.627\.62s\) is slower than a PowerMH step \(4\.974\.97s\), so a PreSTO\-EntropyCut call costs only1\.45×1\.45\\timesa step and the speedup reaches2\.85×2\.85\\times, versus1\.61×1\.61\\timesfor PreSTO\-PowerMH\.\(3\)The gain is smallest when few prefetched proposals are realized relative to the cost of a call: of the five settings below1\.25×1\.25\\times, the four of PreSTO\-PowerMH \(MBPP with both Qwen3 models, and HumanEval and MMLU with Qwen3\.5\-9B\) realize only1\.961\.96–2\.722\.72transitions per call, each costing about2×2\\timesa PowerMH step, and PreSTO\-EntropyCut on MBPP with Qwen3\-4B realizes3\.513\.51per call, each costing2\.7×2\.7\\timesan EntropyCut step\.

### 5\.2Case Studies

Case Study 1: Model\-call efficiency\.We decompose cumulative model\-call time into realized MH transitions per model call \(chain progress\) and time per call \(cost\)\. Figure[5](https://arxiv.org/html/2610.13171#S5.F5)reports these metrics with Qwen3\.5\-9B on LCB V6, and Figure[1](https://arxiv.org/html/2610.13171#S1.F1)places all 105 settings by the two factors of the speedup \([20](https://arxiv.org/html/2610.13171#A4.E20)\): the reduction in model calls and the change in time per call\.

Figure 5:Under LCB V6 and Qwen3\.5\-9B, PreSTO \(Npf=20N\_\{\\mathrm\{pf\}\}=20, default BFS traversal\) speeds up PowerMH by1\.44×1\.44\\timesin mean cumulative model\-call time: it makes4\.92×4\.92\\timesfewer model calls \(a ratio of means\), each taking3\.42×3\.42\\timesas long, while the per\-prompt transitions per call average4\.964\.96\(Appendix[D\.2](https://arxiv.org/html/2610.13171#A4.SS2)\)\.Table 2:Under dataset LCB V6 and base LLM Qwen3\.5\-9B, raising the prefetch budgetNpfN\_\{\\mathrm\{pf\}\}from88to2020increases the speedup of PreSTO\-PowerMH over PowerMH from1\.20×1\.20\\timesto1\.44×1\.44\\times\. Transitions per call isKKdivided by the mean number of calls, and time per call is the total call time divided by the total number of calls\.PowerMHPreSTO\-PowerMH, prefetch budgetNpfN\_\{\\mathrm\{pf\}\}810121620MH transitions per model call1\.003\.593\.944\.274\.634\.91Time per model call \(s\)5\.3916\.1516\.5617\.5818\.1518\.43Speedup over PowerMH1\.00×\\times1\.20×\\times1\.28×\\times1\.31×\\times1\.38×\\times1\.44×\\timesFrom Figure[5](https://arxiv.org/html/2610.13171#S5.F5), we find that\(1\)PreSTO\-PowerMH is1\.44×1\.44\\timesfaster than PowerMH: it completesK=100K=100transitions in375\.12±35\.08375\.12\_\{\\pm 35\.08\}rather than539\.24±30\.92539\.24\_\{\\pm 30\.92\}seconds\.\(2\)the speedup comes from fewer calls, not cheaper ones: each PreSTO\-PowerMH call realizes4\.96±0\.474\.96\_\{\\pm 0\.47\}transitions instead of one, but takes18\.45±0\.5118\.45\_\{\\pm 0\.51\}rather than5\.39±0\.315\.39\_\{\\pm 0\.31\}seconds\. A PreSTO\-PowerMH call here takes about1818seconds, against10\.510\.5–10\.910\.9seconds for Qwen3\.5\-9B on the other six datasets \(Table[7](https://arxiv.org/html/2610.13171#A5.T7)\), so the speedup is lower than in those settings\. PreSTO\-EntropyCut shows the same pattern on LCB V6 \(1\.91×1\.91\\times\):4\.22±0\.584\.22\_\{\\pm 0\.58\}transitions per call at10\.08±0\.4710\.08\_\{\\pm 0\.47\}rather than4\.64±0\.524\.64\_\{\\pm 0\.52\}seconds; as a ratio of means, it makes4\.15×4\.15\\timesfewer calls, each2\.17×2\.17\\timesas long\.\(3\)across the 105 settings \(Figure[1](https://arxiv.org/html/2610.13171#S1.F1)\), what drives the speedup depends on the sampler\. The log speedup equals the log reduction in calls minus the log increase in time per call; we split its variance between the two terms by their covariances with it \(the shares sum to one\)\. Over PowerMH, the reduction in calls \(1\.94×1\.94\\times–4\.92×4\.92\\times\) takes a95%95\\%share \(R2=0\.78R^\{2\}=0\.78\), because time per call rises by a nearly constant1\.90×1\.90\\times–2\.42×2\.42\\times\. Over EntropyCut and MultiTryMH, the time\-per\-call ratio \(1\.37×1\.37\\times–2\.74×2\.74\\timesand0\.26×0\.26\\times–1\.00×1\.00\\times\) takes94%94\\%and99%99\\%shares \(R2=0\.75R^\{2\}=0\.75and0\.990\.99\), because the reduction in calls varies less \(3\.11×3\.11\\times–4\.52×4\.52\\timesand1\.77×1\.77\\times–2\.05×2\.05\\times\)\.

Case Study 2: Effect of prefetch budget\.We sweepNpf∈\{8,10,12,16,20\}N\_\{\\mathrm\{pf\}\}\\in\\\{8,10,12,16,20\\\}for PreSTO\-PowerMH with the default BFS traversal on LCB V6 with Qwen3\.5\-9B, against the PowerMH run of Case Study 6; all runs share one host and were recorded within three days \(Appendix\)\. Table[2](https://arxiv.org/html/2610.13171#S5.T2)reports chain progress \(transitions per call, speedup over PowerMH\) and the cost of a call; each budget uses a single seed\.

From Table[2](https://arxiv.org/html/2610.13171#S5.T2), we find that\(1\)the speedup grows with the budget up to the defaultNpf=20N\_\{\\mathrm\{pf\}\}=20: fromNpf=8N\_\{\\mathrm\{pf\}\}=8to2020, transitions per call rise from3\.593\.59to4\.914\.91and the speedup from1\.20×1\.20\\timesto1\.44×1\.44\\times\.\(2\)each call slows with the budget, from16\.216\.2to18\.418\.4seconds against5\.45\.4seconds for a PowerMH step, so the speedup grows more slowly than the transitions per call; every prefetched proposal is generated whether or not it is realized\.

Case Study 3: Likelihood and confidence\.PreSTO changes how proposals are scheduled and evaluated, not the MH target, so a sampler and its PreSTO variant should produce terminal traces with the same distribution of token\-normalized log\-likelihood and confidence underp0p\_\{0\}\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)\. We rescore the terminal traces of each pair underp0p\_\{0\}afterK=100K=100transitions and test each statistic with a paired two one\-sided tests \(TOST\) equivalence test at a margin of0\.20\.2baseline standard deviations \(Appendix[E\.3](https://arxiv.org/html/2610.13171#A5.SS3)\)\.

Figure 6:Under base LLM Qwen3\.5\-4B across five datasets, PreSTO\-PowerMH and PowerMH produce closely overlapping distributions of base\-model log\-likelihood and confidence, and the paired TOST finds them equivalent in 7 of the 10 comparisons \(shaded\)\.From Figure[6](https://arxiv.org/html/2610.13171#S5.F6), we find that\(1\)with Qwen3\.5\-4B, the distributions of PreSTO\-PowerMH and PowerMH overlap closely on all five datasets, and the test establishes equivalence in 7 of the 10 comparisons; in the other three, both statistics on AIME and confidence on MATH500, the 90% intervals extend past the margin\.\(2\)the result holds beyond this base LLM: across all pairs that pass the rescoring check of Appendix[E\.3](https://arxiv.org/html/2610.13171#A5.SS3)\(8 for PowerMH and 11 for EntropyCut, two statistics each\), 29 of the 38 tests establish equivalence, and the pooled differences on both statistics lie within the±0\.2\\pm 0\.2\-SD margin \(peq<0\.001p\_\{\\mathrm\{eq\}\}<0\.001\)\.

Case Study 4: Distribution ofϵ\\epsilon\-certainty\.Figures[15](https://arxiv.org/html/2610.13171#A5.F15)and[16](https://arxiv.org/html/2610.13171#A5.F16)in Appendix[E\.4](https://arxiv.org/html/2610.13171#A5.SS4)report the distribution ofϵ\\epsilon\-certainty for all five base LLMs under PreSTO\-PowerMH and PreSTO\-EntropyCut\. We find that\(1\)most decisions areϵ\\epsilon\-certain for every base LLM:56%56\\%–95%95\\%of edges for the Qwen models and67%67\\%–78%78\\%for Gemma4\-12B\-it under PreSTO\-PowerMH, and60%60\\%–92%92\\%for the Qwen models and60%60\\%–93%93\\%for Gemma4\-12B\-it under PreSTO\-EntropyCut\.\(2\)fewer certain decisions leave more branches in theϵ\\epsilon\-rounded tree, so a fixed budget tends to realize fewer transitions per call\. This link to runtime is correlational, because the histograms count all scored decisions rather than realized acceptances\.

\(d\)First prefetched subtree of one prompt

Npf=8N\_\{\\mathrm\{pf\}\}=8Npf=10N\_\{\\mathrm\{pf\}\}=10Npf=12N\_\{\\mathrm\{pf\}\}=12Npf=16N\_\{\\mathrm\{pf\}\}=16Npf=20N\_\{\\mathrm\{pf\}\}=20

Figure 7:Predictive traversal rule against BFS for PreSTO\-PowerMH on LCB V6 with Qwen3\.5\-9B\. \(a–c\) The predictive rule is1\.25×1\.25\\times–1\.37×1\.37\\timesfaster at every prefetch budget because it realizes19%19\\%–33%33\\%more MH transitions per call; points in \(a, b\) are ratios of totals over the 20 prompts, and error bars in \(c\) show±1\\pm 1SD over prompts\. \(d\) First prefetched subtree of prompt 0, a favorable case: 3 transitions against 2 at every budget \(prompts 1–3 in Appendix[E\.5](https://arxiv.org/html/2610.13171#A5.SS5)\)\. Label MH0→k0\\rightarrow k: the sampled path advances the chain from step 0 tokk\. Solid left edges: acceptance; dashed right edges: rejection; orange:ϵ\\epsilon\-rounded subtree \(ϵ=0\.01\\epsilon=0\.01\); blue: sampled path \(endpoint double\-bordered\); gray: other prefetched branches\.Case Study 5: Effect of traversal rules\.We compare the default BFS traversal with the predictive traversal rule, which solves the objective in \([17](https://arxiv.org/html/2610.13171#A3.E17)\) by dynamic programming\. The two rules differ in two ways: the predictive rule weights each candidate by its predicted branch probabilities, and it never selects a request below a deferred one, whereas BFS spends part of its budget on such unreachable requests\. On LCB V6 with Qwen3\.5\-9B, we run PreSTO\-PowerMH with both rules atNpf∈\{8,10,12,16,20\}N\_\{\\mathrm\{pf\}\}\\in\\\{8,10,12,16,20\\\}on the same 20 prompts \(Appendix[E\.5](https://arxiv.org/html/2610.13171#A5.SS5)\)\. Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)details the classifier that the predictive rule uses\.

From Figure[7](https://arxiv.org/html/2610.13171#S5.F7), we find that\(1\)the predictive rule is faster than BFS at every budget, by1\.25×1\.25\\times–1\.37×1\.37\\timesin cumulative model\-call time \(panel \(c\)\), and on 98 of the 100 prompt–budget pairs\.\(2\)the gain comes from fewer model calls: the predictive rule realizes19%19\\%–33%33\\%more transitions per call \(panel \(a\)\), so it needs1\.19×1\.19\\times–1\.33×1\.33\\timesfewer calls, while its time per call is2\.6%2\.6\\%–4\.9%4\.9\\%shorter \(panel \(b\)\)\.\(3\)the gain is largest atNpf=20N\_\{\\mathrm\{pf\}\}=20\(1\.37×1\.37\\times\), where transitions per call rise from4\.914\.91to6\.546\.54\. Panel \(d\) shows the first prefetched subtree of prompt 0 under both rules, and Appendix[E\.5](https://arxiv.org/html/2610.13171#A5.SS5)shows three more prompts\.

Three further case studies compare serving engines \(Case Study 6, Appendix[E\.6](https://arxiv.org/html/2610.13171#A5.SS6)\), predictϵ\\epsilon\-certainty before generation \(Case Study 7, Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)\), and compare PreSTO\-PowerMH with test\-time baselines \(Case Study 8, Appendix[E\.8](https://arxiv.org/html/2610.13171#A5.SS8)\); Appendix[E\.9](https://arxiv.org/html/2610.13171#A5.SS9)shows an example prefetched\-subtree trajectory\.

## 6Conclusion

We study how to accelerate MH\-based power sampling, whose sequential accept/reject decisions force one model call per MH transition\. We propose PreSTO, which prefetches proposals for a subtree of future MH states in one batched call and follows the realized path with the original acceptance rule; for PowerMH, this leaves the MH transition kernel unchanged \(Proposition[1](https://arxiv.org/html/2610.13171#Thmproposition1)\)\. Because the part of a prefetched subtree reached by MH is sparse and nearly unary, our predictive traversal rule allocates the prefetch budget by dynamic programming\. In experiments, across five base LLMs and seven datasets, PreSTO is never slower than its baseline and achieves median speedups of1\.71×1\.71\\timesover PowerMH,1\.91×1\.91\\timesover EntropyCut, and2\.33×2\.33\\timesover MultiTryMH\. The speedup comes from fewer model calls, at a cost of at most3\.1%3\.1\\%of the preallocated KV\-cache pool, and the log\-likelihood and confidence of the outputs pass paired equivalence tests against the baselines in 29 of 38 comparisons\. The predictive traversal rule adds a further1\.25×1\.25\\times–1\.37×1\.37\\timesspeedup over the default BFS traversal on LCB V6 with Qwen3\.5\-9B\.

## Acknowledgments

We thank the CoreWeave AI cloud platform for supporting part of the computational resources used in this work\. Nan Jiang acknowledges support from the Texas Advanced Computing Center \(TACC\) under award CCR25054\. Panagiotis Theodoropoulos was partly supported by the Defense Advanced Research Projects Agency \(DARPA\) through the Artificial Intelligence Quantified \(AIQ\) program, under Cooperative Agreement No\. HR00112520010\. The views, opinions, and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U\.S\. Government\.

## References

- Ahmadi et al\. \(2026\)Minoo Ahmadi, Seyedarmin Azizi, Erfan Baghaei Potraghloo, Mehdi Kamal, and Massoud Pedram\.Chopthin\-Consensus Power Sampling: A Diversity\-Preserving Approach to LLM Decoding\.In*COLM 2026 Workshop on Efficient Reasoning*, 2026\.
- Angelino et al\. \(2014\)Elaine Angelino, Eddie Kohler, Amos Waterland, Margo I\. Seltzer, and Ryan P\. Adams\.Accelerating MCMC via Parallel Predictive Prefetching\.In*Proc\. of the Conference on Uncertainty in Artificial Intelligence \(UAI\)*, pages 22–31, 2014\.
- Arzhantsev et al\. \(2026\)Aleksei Arzhantsev, Otmane Sakhi, and Nicolas Chopin\.Self\-Consistency via Marginal Sharpening\.*arXiv preprint arXiv:2605\.28142*, 2026\.
- Austin et al\. \(2021\)Jacob Austin, Augustus Odena, Maxwell I\. Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J\. Cai, Michael Terry, Quoc V\. Le, and Charles Sutton\.Program Synthesis with Large Language Models\.*arXiv preprint arXiv:2108\.07732*, 2021\.
- Azizi et al\. \(2026\)Seyedarmin Azizi, Erfan Baghaei Potraghloo, Minoo Ahmadi, Souvik Kundu, and Massoud Pedram\.Power\-SMC: Low\-Latency Sequence\-Level Power Sampling for Training\-Free LLM Reasoning\.*arXiv preprint arXiv:2602\.10273*, 2026\.
- Brockwell \(2006\)A\. E\. Brockwell\.Parallel Markov chain Monte Carlo Simulation by Pre\-Fetching\.*Journal of Computational and Graphical Statistics*, 15\(1\):246–261, 2006\.
- Cai et al\. \(2024\)Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D\. Lee, Deming Chen, and Tri Dao\.Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 235, pages 5209–5235, 2024\.
- Calderhead \(2014\)Ben Calderhead\.A General Construction for Parallelizing Metropolis–Hastings Algorithms\.*Proceedings of the National Academy of Sciences*, 111\(49\):17408–17413, 2014\.
- Chen et al\. \(2023\)Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean\-Baptiste Lespiau, Laurent Sifre, and John Jumper\.Accelerating Large Language Model Decoding with Speculative Sampling\.*arXiv preprint arXiv:2302\.01318*, 2023\.
- Chen et al\. \(2021\)M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. de Oliveira Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman, A\. Ray, R\. Puri, G\. Krueger, M\. Petrov, H\. Khlaaf, G\. Sastry, P\. Mishkin, B\. Chan, S\. Gray, N\. Ryder, M\. Pavlov, A\. Power, L\. Kaiser, M\. Bavarian, C\. Winter, P\. Tillet, F\. P\. Such, D\. Cummings, M\. Plappert, F\. Chantzis, E\. Barnes, A\. Herbert\-Voss, W\. H\. Guss, A\. Nichol, A\. Paino, N\. Tezak, J\. Tang, I\. Babuschkin, S\. Balaji, S\. Jain, W\. Saunders, C\. Hesse, A\. N\. Carr, J\. Leike, J\. Achiam, V\. Misra, E\. Morikawa, A\. Radford, M\. Knight, M\. Brundage, M\. Murati, K\. Mayer, P\. Welinder, B\. McGrew, D\. Amodei, S\. McCandlish, I\. Sutskever, and W\. Zaremba\.Evaluating Large Language Models Trained on Code\.*arXiv preprint arXiv:2107\.03374*, 2021\.
- Chen et al\. \(2025\)Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang\.Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2025\.
- Chen et al\. \(2024\)Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen\.Sequoia: Scalable and Robust Speculative Decoding\.volume 37, 2024\.
- Du et al\. \(2024\)Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Holden Lee, Jason Eisner, and Ryan Cotterell\.Principled Gradient\-Based MCMC for Conditional Sampling of Text\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 235, pages 11663–11685, 2024\.
- Du et al\. \(2025\)Weihua Du, Yiming Yang, and Sean Welleck\.Optimizing Temperature for Language Models with Multi\-Sample Inference\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 267, 2025\.
- Emara et al\. \(2026\)Yahya Emara, Mauricio Barba da Costa, Chi\-Chih Chang, Cameron Freer, Tim Vieira, Ryan Cotterell, and Mohamed S\. Abdelfattah\.Faster LLM Inference via Sequential Monte Carlo\.*arXiv preprint arXiv:2604\.15672*, 2026\.
- Faria et al\. \(2024\)Gonçalo Rui Alves Faria, Sweta Agrawal, António Farinhas, Ricardo Rei, José Guilherme Camargo de Souza, and André F\. T\. Martins\.QUEST: Quality\-Aware Metropolis\-Hastings Sampling for Machine Translation\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, volume 37, pages 89042–89068, 2024\.
- Forristal et al\. \(2023\)Jarad Forristal, Fatemehsadat Mireshghallah, Greg Durrett, and Taylor Berg\-Kirkpatrick\.A Block Metropolis\-Hastings Sampler for Controllable Energy\-based Text Generation\.In*Proc\. of the Annual Conference on Computational Natural Language Learning \(CoNLL\)*, pages 403–413, 2023\.
- Guo et al\. \(2025\)Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al\.DeepSeek\-R1: Incentivizing reasoning capability in LLMs via reinforcement learning\.*arXiv preprint arXiv:2501\.12948*, 2025\.
- Guo et al\. \(2026\)Hong Guo, Nianhui Guo, Christoph Meinel, and Haojin Yang\.Sample Where You Struggle: Sharpening Base Model Reasoning via Entropy\-Guided Power Sampling\.*arXiv preprint arXiv:2606\.09926*, 2026\.
- Hastings \(1970\)W\. K\. Hastings\.Monte Carlo sampling methods using Markov chains and their applications\.*Biometrika*, 57\(1\):97–109, 1970\.
- He et al\. \(2025\)Andre He, Daniel Fried, and Sean Welleck\.Rewarding the unlikely: Lifting GRPO beyond distribution sharpening\.*arXiv preprint arXiv:2506\.02355*, 2025\.
- He et al\. \(2026\)Jiajun He, Zongyu Guo, José Miguel Hernández\-Lobato, and Yuanqi Du\.Recipes for Steering and Scaling LLMs via Sampling\.*arXiv preprint arXiv:2608\.26120*, 2026\.
- Hendrycks et al\. \(2021a\)Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt\.Measuring Massive Multitask Language Understanding\.In*Proc\. of the International Conference on Learning Representations \(ICLR\)*, 2021a\.
- Hendrycks et al\. \(2021b\)Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt\.Measuring Mathematical Problem Solving With the MATH Dataset\.In*NeurIPS Datasets and Benchmarks*, 2021b\.
- Hu et al\. \(2025\)Jingcheng Hu, Yinmin Zhang, Qi Han, Daxin Jiang, Xiangyu Zhang, and Heung\-Yeung Shum\.Open\-Reasoner\-Zero: An open source approach to scaling up reinforcement learning on the base model\.*arXiv preprint arXiv:2503\.24290*, 2025\.
- Jain et al\. \(2025\)Naman Jain, King Han, Alex Gu, Wen\-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar\-Lezama, Koushik Sen, and Ion Stoica\.LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code\.In*Proc\. of the International Conference on Learning Representations \(ICLR\)*, 2025\.
- Ji et al\. \(2026\)Xiaotong Ji, Rasul Tutunov, Matthieu Zimmer, and Haitham Bou Ammar\.Scalable Power Sampling: Unlocking Efficient, Training\-Free Reasoning for LLMs via Distribution Sharpening\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, 2026\.
- Karan and Du \(2026\)Aayush Karan and Yilun Du\.Reasoning with Sampling: Your Base Model is Smarter Than You Think\.In*Proc\. of the International Conference on Learning Representations \(ICLR\)*, 2026\.
- Kwon et al\. \(2023\)Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E\. Gonzalez, Hao Zhang, and Ion Stoica\.Efficient Memory Management for Large Language Model Serving with PagedAttention\.In*Proc\. of the ACM Symposium on Operating Systems Principles \(SOSP\)*, pages 611–626, 2023\.
- Lakens \(2017\)Daniël Lakens\.Equivalence Tests: A Practical Primer forttTests, Correlations, and Meta\-Analyses\.*Social Psychological and Personality Science*, 8\(4\):355–362, 2017\.
- Leviathan et al\. \(2023\)Yaniv Leviathan, Matan Kalman, and Yossi Matias\.Fast Inference from Transformers via Speculative Decoding\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 202, pages 19274–19286, 2023\.
- Li et al\. \(2025\)Marvin Li, Aayush Karan, and Sitan Chen\.Blink of an eye: a simple theory for feature localization in generative models\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, 2025\.
- Li et al\. \(2024a\)Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang\.EAGLE\-2: Faster Inference of Language Models with Dynamic Draft Trees\.In*Proc\. of the Conference on Empirical Methods in Natural Language Processing \(EMNLP\)*, pages 7421–7432, 2024a\.
- Li et al\. \(2024b\)Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang\.EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 235, pages 28935–28948, 2024b\.
- Li et al\. \(2022\)Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po\-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J\. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals\.Competition\-level code generation with AlphaCode\.*Science*, 378\(6624\):1092–1097, 2022\.
- Lightman et al\. \(2024\)Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe\.Let’s Verify Step by Step\.In*Proc\. of the International Conference on Learning Representations \(ICLR\)*, 2024\.
- Liu et al\. \(2000\)Jun S\. Liu, Faming Liang, and Wing Hung Wong\.The Multiple\-Try Method and Local Optimization in Metropolis Sampling\.*Journal of the American Statistical Association*, 95\(449\):121–134, 2000\.
- Meng et al\. \(2026\)Zibin Meng, Peng Xie, and Kani Chen\.Depth\-Entropy Guided Sampling for Training\-Free LLM Reasoning\.*arXiv preprint arXiv:2607\.09693*, 2026\.
- Metropolis et al\. \(1953\)Nicholas Metropolis, Arianna W\. Rosenbluth, Marshall N\. Rosenbluth, Augusta H\. Teller, and Edward Teller\.Equation of state calculations by fast computing machines\.*Journal of Chemical Physics*, 21\(6\):1087–1092, 1953\.
- Miao et al\. \(2024\)Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia\.SpecInfer: Accelerating Large Language Model Serving with Tree\-based Speculative Inference and Verification\.In*Proc\. of the ACM International Conference on Architectural Support for Programming Languages and Operating Systems \(ASPLOS\)*, pages 932–949, 2024\.
- Mireshghallah et al\. \(2022\)Fatemehsadat Mireshghallah, Kartik Goyal, and Taylor Berg\-Kirkpatrick\.Mix and Match: Learning\-Free Controllable Text Generation using Energy Language Models\.In*Proc\. of the Annual Meeting of the Association for Computational Linguistics \(ACL\)*, pages 401–415, 2022\.
- Mittal et al\. \(2026\)Sarthak Mittal, Leo Gagnon, and Guillaume Lajoie\.Beyond Distribution Sharpening: The Importance of Task Rewards\.In*Proc\. of the Annual Conference on Language Modeling \(COLM\)*, 2026\.
- Neal \(2001\)Radford M\. Neal\.Annealed importance sampling\.*Statistics and Computing*, 11\(2\):125–139, 2001\.
- Nguyen et al\. \(2026\)Tu Nguyen, Matthieu Zimmer, Rasul Tutunov, Xiaotong Ji, and Haitham Bou Ammar\.The Model Knows, the Decoder Finds: Future Value Guided Particle Power Sampling\.In*ICML 2026 Workshop on Structured Probabilistic Inference & Generative Modeling*, 2026\.
- Rein et al\. \(2024\)David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R\. Bowman\.GPQA: A graduate\-level Google\-proof Q&A benchmark\.In*Proc\. of the Annual Conference on Language Modeling \(COLM\)*, 2024\.
- Sambridge \(2014\)Malcolm Sambridge\.A Parallel Tempering algorithm for probabilistic sampling and optimization\.*Geophysical Journal International*, 196\(1\):357–374, 2014\.
- Scheufele et al\. \(2026\)Hannah Scheufele, Peter Blohm, and Vikas Garg\.Temperature Scaling in Discrete Sequence \(Language\) Models\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 306, 2026\.
- Schuirmann \(1987\)Donald J\. Schuirmann\.A comparison of the two one\-sided tests procedure and the power approach for assessing the equivalence of average bioavailability\.*Journal of Pharmacokinetics and Biopharmaceutics*, 15\(6\):657–680, 1987\.
- Shao et al\. \(2026\)Rulin Shao, Shuyue Stella Li, Rui Xin, Scott Geng, Yiping Wang, Sewoong Oh, Simon Shaolei Du, Nathan Lambert, Sewon Min, Ranjay Krishna, Yulia Tsvetkov, Hannaneh Hajishirzi, Pang Wei Koh, and Luke Zettlemoyer\.Spurious Rewards: Rethinking Training Signals in RLVR\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, 2026\.
- Shao et al\. \(2024\)Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, Y\. K\. Li, Y\. Wu, and Daya Guo\.DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models\.*arXiv preprint arXiv:2402\.03300*, 2024\.
- Stern et al\. \(2018\)Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit\.Blockwise Parallel Decoding for Deep Autoregressive Models\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, pages 10107–10116, 2018\.
- Stiennon et al\. \(2020\)Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel M\. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F\. Christiano\.Learning to Summarize with Human Feedback\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2020\.
- Strid \(2010\)Ingvar Strid\.Efficient parallelisation of Metropolis–Hastings algorithms using a prefetching approach\.*Computational Statistics & Data Analysis*, 54\(11\):2814–2835, 2010\.
- Sun et al\. \(2024\)Hanshi Sun, Momin Haider, Ruiqi Zhang, Huitao Yang, Jiahao Qiu, Ming Yin, Mengdi Wang, Peter L\. Bartlett, and Andrea Zanette\.Fast Best\-of\-N Decoding via Speculative Rejection\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, volume 37, pages 32630–32652, 2024\.
- Tomihari and Sato \(2026\)Akiyoshi Tomihari and Issei Sato\.Power Distribution Bridges Sampling, Self\-Reward RL, and Self\-Distillation\.*arXiv preprint arXiv:2605\.04542*, 2026\.
- Troshin et al\. \(2025\)Sergey Troshin, Wafaa Mohammed, Yan Meng, Christof Monz, Antske Fokkens, and Vlad Niculae\.Control the Temperature: Selective Sampling for Diverse and High\-Quality LLM Outputs\.In*Proc\. of the Annual Conference on Language Modeling \(COLM\)*, 2025\.
- Xia et al\. \(2024\)Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui\.Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding\.In*Findings of the Association for Computational Linguistics \(ACL\)*, pages 7655–7671, 2024\.
- Ye and Lu \(2024\)Guifeng Ye and Shaowen Lu\.Prefetching\-based Multiproposal Markov Chain Monte Carlo Algorithm\.*IEEE Transactions on Artificial Intelligence*, 5\(9\):4493–4505, 2024\.
- Zenn and Geiping \(2026\)Johannes Zenn and Jonas Geiping\.When are likely answers right? On Sequence Probability and Correctness in LLMs\.In*ICML 2026 Workshop on Structured Probabilistic Inference & Generative Modeling*, 2026\.
- Zhao et al\. \(2024\)Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse\.Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo\.In*Proc\. of the International Conference on Machine Learning \(ICML\)*, volume 235, pages 60704–60748, 2024\.
- Zheng et al\. \(2024\)Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E\. Gonzalez, Clark W\. Barrett, and Ying Sheng\.SGLang: Efficient Execution of Structured Language Model Programs\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2024\.
- Zhou et al\. \(2026\)Felix Zhou, Anay Mehrotra, and Quanquan C\. Liu\.Reasoning with Sampling: Cutting at Decision Points\.*arXiv preprint arXiv:2605\.30327*, 2026\.
- Zhu et al\. \(2024\)Yuqi Zhu, Jia Li, Ge Li, Yunfei Zhao, Jia Li, Zhi Jin, and Hong Mei\.Hot or Cold? Adaptive Temperature Sampling for Code Generation with Large Language Models\.In*Proc\. of the AAAI Conference on Artificial Intelligence \(AAAI\)*, pages 437–445, 2024\.

Contents

## Appendix AExtended Related Work

PreSTO draws on three lines of work\. Power\-sampling methods define the target and the samplers that PreSTO accelerates\. Speculative decoding and MCMC prefetching are two established ways to break serial dependence during sampling\. For each line, we summarize the problem it addresses, the mechanism its methods share, and the trade\-offs among them\.

### A\.1Sampling from the Power Distribution

Power sampling draws complete responses fromπα∝p0α\\pi\_\{\\alpha\}\\propto p\_\{0\}^\{\\alpha\}withα\>1\\alpha\>1\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)\. Raising the sequence likelihood to a power concentrates probability on responses that the base model finds likely as a whole, the same construction that annealing and parallel tempering use to control how concentrated a target is\([Neal, 2001](https://arxiv.org/html/2610.13171#bib.bib43);[Sambridge, 2014](https://arxiv.org/html/2610.13171#bib.bib46)\)\.

Why token\-level sharpening is not enough\.Token\-level temperature scaling and filtering\([Zhu et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib63);[Du et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib14);[Troshin et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib56)\)sharpen each next\-token distribution and renormalize at every prefix\. The exact next\-token conditional of the power target is instead

πα\(xt∣𝐱0:t−1\)∝p0\(xt∣𝐱0:t−1\)αZα\(𝐱0:t\),whereZα\(𝐱0:t\)=∑𝐱t\+1:np0\(𝐱t\+1:n∣𝐱0:t\)α\.\\pi\_\{\\alpha\}\(x\_\{t\}\\mid\\mathbf\{x\}\_\{0:t\-1\}\)\\;\\propto\\;p\_\{0\}\(x\_\{t\}\\mid\\mathbf\{x\}\_\{0:t\-1\}\)^\{\\alpha\}\\,Z\_\{\\alpha\}\(\\mathbf\{x\}\_\{0:t\}\),\\qquad\\text\{where\}\\qquad Z\_\{\\alpha\}\(\\mathbf\{x\}\_\{0:t\}\)=\\sum\_\{\\mathbf\{x\}\_\{t\+1:n\}\}p\_\{0\}\(\\mathbf\{x\}\_\{t\+1:n\}\\mid\\mathbf\{x\}\_\{0:t\}\)^\{\\alpha\}\.Token\-level temperatureτ=1/α\\tau=1/\\alphakeeps the first factor and dropsZαZ\_\{\\alpha\}\. Forα\>1\\alpha\>1,ZαZ\_\{\\alpha\}is large when the continuations of a prefix concentrate on a few high\-likelihood completions, so the power target prefers such prefixes, whereas low\-temperature decoding cannot distinguish them\. BecauseZαZ\_\{\\alpha\}sums over exponentially many continuations, every power\-sampling method must avoid it, approximate it, or change the target\. Existing methods follow three routes\.

MCMC over complete sequences\.MH needs the target only up to a constant, so it avoidsZαZ\_\{\\alpha\}entirely: it compares complete sequences through the ratioπα​\(𝐲\)/πα​\(𝐱\)=\(p0​\(𝐲\)/p0​\(𝐱\)\)α\\pi\_\{\\alpha\}\(\\mathbf\{y\}\)/\\pi\_\{\\alpha\}\(\\mathbf\{x\}\)=\\bigl\(p\_\{0\}\(\\mathbf\{y\}\)/p\_\{0\}\(\\mathbf\{x\}\)\\bigr\)^\{\\alpha\}\. The main design choice is the proposal\. Earlier MCMC samplers for controlled generation with energy\-based targets edit one position at a time and need many steps to make coordinated changes across a sequence\([Mireshghallah et al\., 2022](https://arxiv.org/html/2610.13171#bib.bib41)\)\. Regenerating a complete sequence or a suffix with an LLM instead makes large, coherent edits whose proposal probabilities come from the same forward pass\([Forristal et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib17);[Faria et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib16)\)\. PowerMH applies suffix regeneration toπα\\pi\_\{\\alpha\}with a blockwise schedule\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\), and later variants keep this structure while changing where cuts are placed or how many candidates each step considers\. EntropyCut\([Zhou et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib62)\)places cuts using token entropy, and MultiTryMH, a variant of the entropy\-guided sampler of[Guo et al\. \(2026\)](https://arxiv.org/html/2610.13171#bib.bib19), draws several candidate suffixes per step and moves with a multiple\-try Metropolis update\([Liu et al\., 2000](https://arxiv.org/html/2610.13171#bib.bib37)\)\. Other variants add terms to the target\([Meng et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib38)\)\. These samplers share three costs: each transition regenerates on average about half of the response when the cut is uniform, each stage needs many transitions, and transitions are serial because every proposal is conditioned on the current state\.

Forward approximations\.Forward methods generate left to right and estimateZαZ\_\{\\alpha\}rather than drop it\. Particle methods propagate a population of partial sequences from a tractable proposal, such as low\-temperature decoding, reweight them at every step by the ratio of target to proposal, and resample to discard low\-weight prefixes\. Without twisting, these intermediate weights ignore the future termZαZ\_\{\\alpha\}; twisted variants learn approximations ofZαZ\_\{\\alpha\}so that the intermediate weights account for it\([Zhao et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib60)\)\. For power targets, these samplers are consistent as the number of particles grows\([Azizi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib5);[He et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib22)\), and in practice their quality depends on resampling rules that prevent weight degeneracy and particle collapse\([Ahmadi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib1)\)\. Lookahead methods instead estimateZα\(𝐱0:t\)Z\_\{\\alpha\}\(\\mathbf\{x\}\_\{0:t\}\)directly by sampling a few continuations for each candidate token, and use the estimate to correct the next\-token distribution\([Ji et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib27);[Nguyen et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib44)\)\. Both families parallelize naturally across particles or rollouts\. Their bias and variance, however, depend on the number of particles or rollouts, and they never revise a token; resampling only drops or duplicates whole prefixes\.

Changing or amortizing the target\.A third route changes what is sampled or moves the cost into training\. Sharpening the sequence likelihood can favor a single high\-likelihood reasoning trace over an answer supported by many distinct traces, so marginal sharpening sharpens the distribution over final answers instead\([Arzhantsev et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib3)\)\. Distillation\-style methods fine\-tune the model so that ordinary sampling approximates a powered or low\-temperature sequence distribution, which removes the inference\-time overhead at the price of training\([Tomihari and Sato, 2026](https://arxiv.org/html/2610.13171#bib.bib55);[Scheufele et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib47)\)\. Evidence on when sharpening helps is mixed: raising sequence likelihood through decoding need not improve correctness\([Zenn and Geiping, 2026](https://arxiv.org/html/2610.13171#bib.bib59)\), and reward\-trained models can gain in ways that sharpening does not recover\([Mittal et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib42)\)\.

### A\.2Tree\-based Speculative Decoding

Tree\-based speculative decoding \(TreeSD\) is the closest counterpart to PreSTO in the speculative\-decoding literature, because it also spends extra parallel computation on work that may be discarded in order to reduce the number of serial model calls\. We first describe the draft\-then\-verify scheme that TreeSD builds on, then how trees extend it, and finally how PreSTO differs\.

Draft\-then\-verify decoding\.Autoregressive decoding calls the target model once per token, and these calls cannot be batched because each token depends on the previous one\. Speculative decoding breaks this dependence with a cheap drafter that proposes several future tokens\([Stern et al\., 2018](https://arxiv.org/html/2610.13171#bib.bib51);[Xia et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib57)\)\. The target model then scores all of them in a single forward pass, and a verification rule commits the longest accepted prefix together with one token drawn from a corrected distribution\([Leviathan et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib31);[Chen et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib9)\)\. With the rejection\-based rule, the committed tokens follow the target model’s distribution exactly, so drafter quality affects only speed\. Every pass commits at least one token, and the expected number of tokens committed per pass grows with the drafter’s acceptance rate\.

Drafting a tree of continuations\.A chain of draft tokens is truncated at its first rejected token, so one early rejection wastes all later draft work\. Tree\-based methods instead draft several alternative continuations at each position, and verify all branches in one pass with a tree\-structured attention mask, so that each branch attends only to its own ancestors\([Miao et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib40)\)\. The target model can then commit whichever branch is accepted furthest, which raises the expected number of tokens committed per pass at the cost of scoring more candidate tokens\. In all of these methods, the nodes of the tree are draft*tokens*, the branching reflects uncertainty about what the target model will say next, and a verification pass ends with a single committed prefix\.

Better drafters\.A second line of work raises the acceptance rate of the drafter itself\. Extra decoding heads attached to the target model draft several positions at once without a separate drafter model\([Cai et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib7)\), and autoregression at the level of the target model’s features gives a drafter that tracks the target more closely\([Li et al\., 2024b](https://arxiv.org/html/2610.13171#bib.bib34)\)\. Better drafters shift the balance between how many tokens are drafted and how many are accepted, and so change which tree shapes are worth verifying\.

Tree construction as budget allocation\.For a fixed verification budget, i\.e\., a fixed number of nodes per pass, a tree can take many shapes, so tree construction is a budget\-allocation problem\. Early methods use a static shape\([Miao et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib40);[Cai et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib7)\)\. Later methods add branches where the drafter is confident, since those nodes are more likely to be accepted\([Li et al\., 2024a](https://arxiv.org/html/2610.13171#bib.bib33)\), or choose the tree shape by dynamic programming over estimated acceptance rates\([Chen et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib12)\)\. These approaches share one principle: under a node budget, expand the nodes whose expected contribution to the committed prefix is largest\.

Relaxing exact verification\.Exact rejection is not the only option\. SMC\-based variants weight and resample draft blocks instead of truncating at the first rejected token\. They accept a finite\-particle approximation in exchange for using more of the drafted work, and have been applied to power targets\([Emara et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib15)\)\. This differs from PreSTO in that the output is no longer exact for the target, whereas PreSTO preserves the PowerMH trajectory\.

Relation to PreSTO\.PreSTO and TreeSD both use a tree to batch evaluations that would otherwise be serial, both leave the law of the underlying sampler unchanged \(for PreSTO\-PowerMH, the law of the PowerMH chain, notπα\\pi\_\{\\alpha\}itself\), and both face the same question of where to spend a limited speculative budget, so TreeSD’s budget\-allocation arguments carry over to our setting\. The two trees encode different objects, however\. In TreeSD, a branch is an alternative draft\-token continuation, and verification commits an accepted token prefix\. In PreSTO, a branch is an accept/reject outcome of a complete\-sequence MH proposal, and following the realized MH decisions reproduces the sequential PowerMH trajectory\. The unit of progress also differs: every visited expanded node in PreSTO advances the chain by one MH transition, whether the proposal is accepted or rejected, while a TreeSD node contributes only if it lies on the accepted prefix\. Finally, the cost structure differs\. In TreeSD, a cheap drafter proposes the nodes, and only the target model’s verification pass is expensive\. PreSTO has no cheap drafter: every node is a full suffix that the proposal LLM must generate, the same work as one sequential PowerMH proposal\. Expanding the full tree would spend most of this work on nodes off the realized path, so PreSTO confines speculation to a budgeted subtree\.

### A\.3MCMC Prefetching

Parallel MCMC methods typically run many independent chains, parallelize the evaluation of the target density, or speculate on the future of a single chain\. Prefetching is the third approach\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6);[Strid, 2010](https://arxiv.org/html/2610.13171#bib.bib53)\)\. It rests on one observation: from any state, the nextddaccept/reject outcomes form a binary tree of depthdd, and the chain follows exactly one root\-to\-leaf path\. Proposals for every node can be drawn in advance, so the expensive target evaluations at all nodes can run in parallel\. The realized path is then read off with the usual acceptance uniforms, so the chain has exactly the law of sequential MH\.

Evaluating the whole tree is wasteful\. It has2d−12^\{d\}\-1decision nodes, of which onlyddlie on the realized path, so the speedup obtained fromppparallel workers grows only logarithmically inpp\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6)\)\. Later methods therefore evaluate only the nodes most likely to lie on the realized path\. Static prefetching uses the acceptance rate: when acceptance is low, rejection branches dominate, and the tree can be restricted to long rejection chains\([Strid, 2010](https://arxiv.org/html/2610.13171#bib.bib53)\)\. Predictive prefetching uses a cheap approximation of the target to estimate each branch probability, and still decides every realized transition with the exact target\([Angelino et al\., 2014](https://arxiv.org/html/2610.13171#bib.bib2)\)\.

A different approach parallelizes within one transition by drawing several candidates from the current state, whose target evaluations can run in parallel\. Multiple\-try Metropolis selects one candidate with probability proportional to its weight and accepts or rejects it with a corrected acceptance probability\([Liu et al\., 2000](https://arxiv.org/html/2610.13171#bib.bib37)\)\. Multiproposal MH instead moves according to a Markov chain over the candidate set\([Calderhead, 2014](https://arxiv.org/html/2610.13171#bib.bib8)\)\. Both preserve the stationary distribution but change the transition kernel\. Multiproposal steps can be combined with prefetching by expanding a tree of multiproposal steps\([Ye and Lu, 2024](https://arxiv.org/html/2610.13171#bib.bib58)\)\. MultiTryMH\([Guo et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib19)\)applies multiple\-try Metropolis toπα\\pi\_\{\\alpha\}, drawing its candidate suffixes in parallel; PreSTO is complementary to this within\-transition parallelism, and PreSTO\-MultiTryMH prefetches across MultiTryMH transitions\.

## Appendix BImplementation and Correctness of PreSTO

### B\.1Computing Log\-Acceptance Probabilities

We follow the standard steps to derive a simplified expression for the suffix\-resampling log\-acceptance probability in \([6](https://arxiv.org/html/2610.13171#S3.E6)\) by specializing the generic MH acceptance rule in \([1](https://arxiv.org/html/2610.13171#S2.E1)\)\.

All states share the same lengthTT: every proposal is generated to the full horizon and does not stop at the end\-of\-sequence token\. Fix a current state𝐱=𝐱0:T\\mathbf\{x\}=\\mathbf\{x\}\_\{0:T\}and a cut indexcc\. At this cut, the proposal retains the prefix𝐱0:c\\mathbf\{x\}\_\{0:c\}and samples a new suffix𝐲c\+1:T∼qτ\(⋅∣𝐱0:c\)\\mathbf\{y\}\_\{c\+1:T\}\\sim q\_\{\\tau\}\(\\cdot\\mid\\mathbf\{x\}\_\{0:c\}\)from the proposal LLM\. The resulting candidate is𝐲=\(𝐱0:c,𝐲c\+1:T\)\\mathbf\{y\}=\(\\mathbf\{x\}\_\{0:c\},\\mathbf\{y\}\_\{c\+1:T\}\), so𝐲0:c=𝐱0:c\\mathbf\{y\}\_\{0:c\}=\\mathbf\{x\}\_\{0:c\}\. We writeq⁡\(𝐲∣𝐱,c\)q\(\\mathbf\{y\}\\mid\\mathbf\{x\},c\)for the MH proposal kernel conditional on the cut, to distinguish it from the token\-level LLM conditionalsqτq\_\{\\tau\}\. PowerMH drawsc∼Unif​\{0,…,T−1\}c\\sim\\mathrm\{Unif\}\\\{0,\\ldots,T\-1\\\}independently of the state, and the reverse move from𝐲\\mathbf\{y\}to𝐱\\mathbf\{x\}uses the same cut\. Each cut\-conditional kernel with the acceptance probability below isπα\\pi\_\{\\alpha\}\-reversible, and so is their uniform mixture overcc\. For this candidate, the acceptance rule in \([1](https://arxiv.org/html/2610.13171#S2.E1)\) becomes

A\(𝐲,𝐱\)=min\{1,πα\(𝐲1:T∣𝐱0\)q\(𝐱∣𝐲,c\)πα\(𝐱1:T∣𝐱0\)q\(𝐲∣𝐱,c\)\}\.A\(\\mathbf\{y\},\\mathbf\{x\}\)=\\min\\\!\\left\\\{1,\\;\\frac\{\\pi\_\{\\alpha\}\(\\mathbf\{y\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\\,q\(\\mathbf\{x\}\\mid\\mathbf\{y\},c\)\}\{\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\\,q\(\\mathbf\{y\}\\mid\\mathbf\{x\},c\)\}\\right\\\}\.\(7\)We next simplify the proposal and target ratios in \([7](https://arxiv.org/html/2610.13171#A2.E7)\) separately\.

1. 1\.Proposal log\-ratio\.At the fixed cutcc, the candidate differs from𝐱\\mathbf\{x\}only in the resampled suffix, so the forward proposal probability is q\(𝐲∣𝐱,c\)=qτ\(𝐲c\+1:T∣𝐱0:c\)\.q\(\\mathbf\{y\}\\mid\\mathbf\{x\},c\)=q\_\{\\tau\}\\bigl\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\.The reverse move applies the same cutccto propose𝐱\\mathbf\{x\}from𝐲\\mathbf\{y\}\. It preserves𝐲0:c\\mathbf\{y\}\_\{0:c\}and generates the original suffix𝐱c\+1:T\\mathbf\{x\}\_\{c\+1:T\}\. Using𝐲0:c=𝐱0:c\\mathbf\{y\}\_\{0:c\}=\\mathbf\{x\}\_\{0:c\}, the reverse proposal probability becomes q\(𝐱∣𝐲,c\)=qτ\(𝐱c\+1:T∣𝐲0:c\)=qτ\(𝐱c\+1:T∣𝐱0:c\)\.q\(\\mathbf\{x\}\\mid\\mathbf\{y\},c\)=q\_\{\\tau\}\\bigl\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{y\}\_\{0:c\}\\bigr\)=q\_\{\\tau\}\\bigl\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\.Therefore, the log\-proposal ratio is logq⁡\(𝐱∣𝐲,c\)q⁡\(𝐲∣𝐱,c\)=logqτ\(𝐱c\+1:T∣𝐱0:c\)−logqτ\(𝐲c\+1:T∣𝐱0:c\)\.\\log\\frac\{q\(\\mathbf\{x\}\\mid\\mathbf\{y\},c\)\}\{q\(\\mathbf\{y\}\\mid\\mathbf\{x\},c\)\}=\\log q\_\{\\tau\}\\bigl\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\-\\log q\_\{\\tau\}\\bigl\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\.\(8\)
2. 2\.Target log\-ratio\.By the stage target \([4](https://arxiv.org/html/2610.13171#S2.E4)\) withℓ​B=T\\ell B=T,πα\(𝐱1:T∣𝐱0\)∝p0\(𝐱1:T∣𝐱0\)α\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\\propto p\_\{0\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)^\{\\alpha\}\. Because the numerator and denominator use the same prompt and the same fixed lengthTT, their common normalizing constant cancels: πα\(𝐲1:T∣𝐱0\)πα\(𝐱1:T∣𝐱0\)=\(p0\(𝐲1:T∣𝐱0\)p0\(𝐱1:T∣𝐱0\)\)α\.\\frac\{\\pi\_\{\\alpha\}\(\\mathbf\{y\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}\{\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}=\\left\(\\frac\{p\_\{0\}\(\\mathbf\{y\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}\{p\_\{0\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\right\)^\{\\\!\\alpha\}\.Since𝐲1:c=𝐱1:c\\mathbf\{y\}\_\{1:c\}=\\mathbf\{x\}\_\{1:c\}, autoregressively factorizing each term on the right\-hand side at the cut gives p0\(𝐲1:T∣𝐱0\)\\displaystyle p\_\{0\}\(\\mathbf\{y\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)=p0\(𝐱1:c∣𝐱0\)p0\(𝐲c\+1:T∣𝐱0:c\),\\displaystyle=p\_\{0\}\(\\mathbf\{x\}\_\{1:c\}\\mid\\mathbf\{x\}\_\{0\}\)\\,p\_\{0\}\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\),p0\(𝐱1:T∣𝐱0\)\\displaystyle p\_\{0\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)=p0\(𝐱1:c∣𝐱0\)p0\(𝐱c\+1:T∣𝐱0:c\)\.\\displaystyle=p\_\{0\}\(\\mathbf\{x\}\_\{1:c\}\\mid\\mathbf\{x\}\_\{0\}\)\\,p\_\{0\}\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)\.Canceling the common prefix probabilityp0\(𝐱1:c∣𝐱0\)p\_\{0\}\(\\mathbf\{x\}\_\{1:c\}\\mid\\mathbf\{x\}\_\{0\}\)and taking logarithms yields logπα\(𝐲1:T∣𝐱0\)πα\(𝐱1:T∣𝐱0\)=α\(logp0\(𝐲c\+1:T∣𝐱0:c\)−logp0\(𝐱c\+1:T∣𝐱0:c\)\)\.\\log\\frac\{\\pi\_\{\\alpha\}\(\\mathbf\{y\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}\{\\pi\_\{\\alpha\}\(\\mathbf\{x\}\_\{1:T\}\\mid\\mathbf\{x\}\_\{0\}\)\}=\\alpha\\Bigl\(\\log p\_\{0\}\\bigl\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\-\\log p\_\{0\}\\bigl\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\\bigr\)\\Bigr\)\.\(9\)
3. 3\.Combined log\-ratio\.Taking the logarithm of the acceptance rule in \([7](https://arxiv.org/html/2610.13171#A2.E7)\), usinglog⁡min⁡\{1,r\}=min⁡\{0,log⁡r\}\\log\\min\\\{1,r\\\}=\\min\\\{0,\\log r\\\}, and substituting \([8](https://arxiv.org/html/2610.13171#A2.E8)\) and \([9](https://arxiv.org/html/2610.13171#A2.E9)\) yields logA\(𝐲,𝐱\)=min\{0,\\displaystyle\\log A\(\\mathbf\{y\},\\mathbf\{x\}\)=\\min\\Bigl\\\{0,logqτ\(𝐱c\+1:T∣𝐱0:c\)−logqτ\(𝐲c\+1:T∣𝐱0:c\)\\displaystyle\\log q\_\{\\tau\}\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)\-\\log q\_\{\\tau\}\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)\+α\(logp0\(𝐲c\+1:T∣𝐱0:c\)−logp0\(𝐱c\+1:T∣𝐱0:c\)\)\},\\displaystyle\+\\alpha\\bigl\(\\log p\_\{0\}\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)\-\\log p\_\{0\}\(\\mathbf\{x\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)\\bigr\)\\Bigr\\\},which is \([6](https://arxiv.org/html/2610.13171#S3.E6)\) withc1c\_\{1\}replaced bycc\. Each suffix log\-probability on the right\-hand side is evaluated by summing token\-level conditional log\-probabilities from the serving engine\. For example, logqτ\(𝐲c\+1:T∣𝐱0:c\)=∑t=c\+1Tlogqτ\(yt∣𝐱0:c,𝐲c\+1:t−1\)\.\\log q\_\{\\tau\}\(\\mathbf\{y\}\_\{c\+1:T\}\\mid\\mathbf\{x\}\_\{0:c\}\)=\\sum\_\{t=c\+1\}^\{T\}\\log q\_\{\\tau\}\(y\_\{t\}\\mid\\mathbf\{x\}\_\{0:c\},\\mathbf\{y\}\_\{c\+1:t\-1\}\)\.Evaluating these quantities in the log domain avoids underflow from multiplying many small token probabilities and improves numerical stability\.

In our implementation, the serving engine of the proposal LLM returns these log\-probabilities\. A single batched model call generates candidate suffixes and provides their log\-probabilities under bothqτq\_\{\\tau\}andp0p\_\{0\}, using the same logits with and without temperature scaling\.

### B\.2Exactness of Subtree Prefetching

Reproducing the sequential chain under speculative evaluation is a standard property of MCMC prefetching\([Brockwell, 2006](https://arxiv.org/html/2610.13171#bib.bib6);[Angelino et al\., 2014](https://arxiv.org/html/2610.13171#bib.bib2)\)\. The following result specializes the standard argument to our suffix\-resampling scheme\. We include the proof for completeness, verifying that generating proposals early under Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)does not change the sequential PowerMH trajectory\. Appendix[C](https://arxiv.org/html/2610.13171#A3)then analyzes how many transitions a prefetched subtree yields and which requests to prefetch under a request budget\.

###### Proposition 1\.

Fix an integerK≥0K\\geq 0\. Fork=0,…,Kk=0,\\ldots,K, let𝐱pf\(k\)\\mathbf\{x\}\_\{\\mathrm\{pf\}\}^\{\(k\)\}and𝐱MH\(k\)\\mathbf\{x\}\_\{\\mathrm\{MH\}\}^\{\(k\)\}denote the states afterkkcommitted transitions of PreSTO\-PowerMH and PowerMH, respectively\. Suppose both samplers start from the same state and PreSTO\-PowerMH satisfies the following assumptions:

1. \(A1\)Prefetched proposals satisfy Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)and are generated from the prefix required by the corresponding decision\.
2. \(A2\)Each decision is assigned cut, suffix\-sampling, and acceptance random inputs that follow the PowerMH laws and are independent within and across decisions\. Scheduling and deferral preserve these inputs, and every proposal required by the realized trajectory is eventually evaluated\.
3. \(A3\)Every committed transition uses its assigned proposal and the exact MH acceptance rule in \([1](https://arxiv.org/html/2610.13171#S2.E1)\)\. Both children are retained as possible outcomes; reaching a leaf postpones subsequent decisions to a later batch\.

Then a coupling that uses the same random inputs at corresponding decisions preserves both sampling laws and satisfies

𝐱pf\(k\)=𝐱MH\(k\),for everyk=0,…,K\.\\displaystyle\\mathbf\{x\}\_\{\\mathrm\{pf\}\}^\{\(k\)\}=\\mathbf\{x\}\_\{\\mathrm\{MH\}\}^\{\(k\)\},\\qquad\\text\{ for every \}k=0,\\ldots,K\.Consequently, ifPMHP\_\{\\mathrm\{MH\}\}denotes the PowerMH transition kernel, the kernel of PreSTO\-PowerMH afterKKcommitted transitions isPMHKP\_\{\\mathrm\{MH\}\}^\{K\}\.

###### Proof\.

Assign independent PowerMH random inputs to each decision of the full accept/reject tree, and couple the two executions through these inputs\. Whether a decision is reached in the eventual committed trajectory depends only on its ancestors’ inputs, so its own inputs retain their original conditional law\. Inclusion in the current batch may depend on scheduling; this changes only when the proposal is evaluated\. Preserving deferred inputs and eventually evaluating every required proposal makes the coupling valid across batch boundaries\.

Suppose the executions agree afterk<Kk<Kcommitted transitions\. By Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)and the prefix identity established in Section[3\.2](https://arxiv.org/html/2610.13171#S3.SS2), any intervening accepted proposal preserves the prefix required by a feasible prefetched request\. Rejections leave the state unchanged\. A deferred request is evaluated from the required prefix when it becomes available\. Thus, both executions use the same prefix in the suffix proposal defined by \([5](https://arxiv.org/html/2610.13171#S3.E5)\), and their common suffix\-sampling randomness produces the same candidate\.

The current states and candidates therefore coincide, giving the same MH acceptance probability in \([1](https://arxiv.org/html/2610.13171#S2.E1)\)\. The shared acceptance uniform yields the same decision and next state\. Since the initial states agree, induction establishes equality through transitionKK\. Each committed transition consequently has kernelPMHP\_\{\\mathrm\{MH\}\}, and theKK\-step kernel isPMHKP\_\{\\mathrm\{MH\}\}^\{K\}\. ∎

Remark \(scope\)\.The proof uses PowerMH only through the laws of the per\-decision random inputs in \(A2\) and the acceptance rule in \(A3\)\. In PowerMH the cut law is uniform and does not depend on the state, so every cut in the batch, and the feasibility check of Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), can be drawn before any proposal is generated\.

### B\.3Examples of Prefix Sharing and MH Transitions through the Prefetched Subtree

cached𝐱\\mathbf\{x\}nodev0v\_\{0\}proposal𝐲\\mathbf\{y\}request\(v1,c1\)\(v\_\{1\},c\_\{1\}\)proposal𝐳\\mathbf\{z\}request\(v3,c2\)\(v\_\{3\},c\_\{2\}\)00c2c\_\{2\}c1c\_\{1\}TTshared prefix𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}shared segment𝐱c2\+1:c1\\mathbf\{x\}\_\{c\_\{2\}\+1:c\_\{1\}\}\(a\)Batched suffix\-resampling requests\.\(v0,c0\)\(v\_\{0\},c\_\{0\}\)\(v1,c1\)\(v\_\{1\},c\_\{1\}\)\(v2,c0\)\(v\_\{2\},c\_\{0\}\)\(v3,c2\)\(v\_\{3\},c\_\{2\}\)\(v4,c1\)\(v\_\{4\},c\_\{1\}\)A⁡\(𝐲,𝐱\)A\(\\mathbf\{y\},\\mathbf\{x\}\)A⁡\(𝐳,𝐲\)A\(\\mathbf\{z\},\\mathbf\{y\}\)\(b\)Prefetching tree\.cachednewly added𝐱\\mathbf\{x\}𝐲\\mathbf\{y\}𝐳\\mathbf\{z\}𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}reused twice𝐱c2\+1:c1\\mathbf\{x\}\_\{c\_\{2\}\+1:c\_\{1\}\}reused once𝐱c1\+1:T\\mathbf\{x\}\_\{c\_\{1\}\+1:T\}\(c\)Radix\-tree layout of the KV cache\.

Figure 8:Two batched suffix\-resampling requests, their prefetching tree, and their shared KV cache\.\(a\)Both requests reuse the cached prefix𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}, and the request for𝐲\\mathbf\{y\}also reuses𝐱c2\+1:c1\\mathbf\{x\}\_\{c\_\{2\}\+1:c\_\{1\}\}\.\(b\)Each acceptance \(left\) edge carries the MH acceptance probability computed from the pair of sequences it connects in \(a\)\.\(c\)Radix\-tree representation of the shared KV\-cache segments\.###### Example 4\.

Suppose𝐱0:T\\mathbf\{x\}\_\{0:T\}is cached andc2≤c1c\_\{2\}\\leq c\_\{1\}\. In Figure[8](https://arxiv.org/html/2610.13171#A2.F8)\(a\), the requests for𝐲\\mathbf\{y\}and𝐳\\mathbf\{z\}condition on𝐱0:c1\\mathbf\{x\}\_\{0:c\_\{1\}\}and𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}, respectively\. Both requests reuse the cached prefix𝐱0:c2\\mathbf\{x\}\_\{0:c\_\{2\}\}; the request for𝐲\\mathbf\{y\}also reuses𝐱c2\+1:c1\\mathbf\{x\}\_\{c\_\{2\}\+1:c\_\{1\}\}\. Figure[8](https://arxiv.org/html/2610.13171#A2.F8)\(c\) represents these shared KV\-cache segments as a radix tree, as in SGLang\([Zheng et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib61)\)\. vLLM\([Kwon et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib29)\)instead reuses full, fixed\-size KV\-cache blocks, indexed by hashes that incorporate each block’s token IDs and the preceding block’s hash\. Both implementations avoid repeated computation of cached prefix states while preserving the proposal distribution and autoregressive decoding of each requested suffix\.

###### Example 5\.

After generating the resampled sequences in Example[3](https://arxiv.org/html/2610.13171#Thmexample3), we associate each prefetched proposal with its MH log\-acceptance probability\. In Figure[8](https://arxiv.org/html/2610.13171#A2.F8)\(a\), request\(v1,c1\)\(v\_\{1\},c\_\{1\}\)produces𝐲\\mathbf\{y\}by resampling the suffix of the cached state𝐱\\mathbf\{x\}after cut indexc1c\_\{1\}\. Using \([6](https://arxiv.org/html/2610.13171#S3.E6)\) with cut indexc1c\_\{1\}, we computelog⁡A⁡\(𝐲,𝐱\)\\log A\(\\mathbf\{y\},\\mathbf\{x\}\)and associate it with the acceptance edgev0→v1v\_\{0\}\\to v\_\{1\}in Figure[8](https://arxiv.org/html/2610.13171#A2.F8)\(b\)\. Likewise, request\(v3,c2\)\(v\_\{3\},c\_\{2\}\)proposes𝐳\\mathbf\{z\}from𝐲\\mathbf\{y\}\. We computelog⁡A⁡\(𝐳,𝐲\)\\log A\(\\mathbf\{z\},\\mathbf\{y\}\)using cut indexc2c\_\{2\}and associate it with the acceptance edgev1→v3v\_\{1\}\\to v\_\{3\}\.

We simulate the sequential MH decisions by traversing the prefetched subtree in Figure[8](https://arxiv.org/html/2610.13171#A2.F8)\(b\) from its root\. At nodev0v\_\{0\}, drawu∼Unif⁡\(0,1\)u\\sim\\mathrm\{Unif\}\(0,1\)and select the next node as

vnext=\{v1,if​u≤A⁡\(𝐲,𝐱\),v2,otherwise,v\_\{\\mathrm\{next\}\}=\\begin\{cases\}v\_\{1\},&\\text\{if \}u\\leq A\(\\mathbf\{y\},\\mathbf\{x\}\),\\\\ v\_\{2\},&\\text\{otherwise\},\\end\{cases\}whereA⁡\(𝐲,𝐱\)A\(\\mathbf\{y\},\\mathbf\{x\}\)is the MH acceptance probability of𝐲\\mathbf\{y\}from𝐱\\mathbf\{x\}\. The realization in Figure[2](https://arxiv.org/html/2610.13171#S3.F2)accepts𝐲\\mathbf\{y\}, so the traversal proceeds fromv0v\_\{0\}tov1v\_\{1\}\. Atv1v\_\{1\}, drawu′∼Unif⁡\(0,1\)u^\{\\prime\}\\sim\\mathrm\{Unif\}\(0,1\)independently\. In this realization,u′\>A⁡\(𝐳,𝐲\)u^\{\\prime\}\>A\(\\mathbf\{z\},\\mathbf\{y\}\), so the second proposal𝐳\\mathbf\{z\}is rejected, yielding the tree pathv0→v1→v4v\_\{0\}\\to v\_\{1\}\\to v\_\{4\}and the corresponding MH trajectory

𝐱\(0\)=𝐱→𝐱\(1\)=𝐲→𝐱\(2\)=𝐲\.\\mathbf\{x\}^\{\(0\)\}=\\mathbf\{x\}\\to\\mathbf\{x\}^\{\(1\)\}=\\mathbf\{y\}\\to\\mathbf\{x\}^\{\(2\)\}=\\mathbf\{y\}\.Together with Examples[1](https://arxiv.org/html/2610.13171#Thmexample1),[2](https://arxiv.org/html/2610.13171#Thmexample2), and[3](https://arxiv.org/html/2610.13171#Thmexample3), this example shows how PreSTO\-PowerMH batches two suffix\-resampling requests into one model call while preserving sequential MH decisions\. Along the illustrated path, this batched call realizes two MH transitions that would require two serial model calls in PowerMH\.

## Appendix CPrefetch Tree Selection under a Request Budget

Appendix[C\.1](https://arxiv.org/html/2610.13171#A3.SS1)fixes the notation for the prefetching tree\. Appendix[C\.2](https://arxiv.org/html/2610.13171#A3.SS2)derives the expected number of MH transitions completed by a prefetched subtree\. Appendix[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)turns this count into an allocation objective with predicted branch probabilities, and Appendix[C\.4](https://arxiv.org/html/2610.13171#A3.SS4)solves it by dynamic programming\.

### C\.1Setup and Notation

We use the prefetching tree of Section[3\.2](https://arxiv.org/html/2610.13171#S3.SS2), with nodesv0,v1,…v\_\{0\},v\_\{1\},\\ldotsand rootv0v\_\{0\}holding the current MH state\. When only the parent–child relation matters, we writevvfor a node andv\+v^\{\+\}andv−v^\{\-\}for its acceptance and rejection children, as in Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3)\. Suppose thatkkof theKKtransitions of the current block are complete \(Algorithm[3\.2](https://arxiv.org/html/2610.13171#S3.SS2)\), and letK′=K−kK^\{\\prime\}=K\-kbe the number that remain\. We cap the tree at depthK′K^\{\\prime\}and write𝒯K′\\mathcal\{T\}\_\{K^\{\\prime\}\}for the resulting finite tree\.

- •*Expandable node\.*A nodevi∈𝒯K′v\_\{i\}\\in\\mathcal\{T\}\_\{K^\{\\prime\}\}withd⁡\(vi\)<K′d\(v\_\{i\}\)<K^\{\\prime\}is expandable if the request at its acceptance childvjv\_\{j\}satisfies Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), that is,cj≤cic\_\{j\}\\leq c\_\{i\}, wherecic\_\{i\}andcjc\_\{j\}are the cut indices ofviv\_\{i\}andvjv\_\{j\}\.
- •*Candidate node\.*An expandable node whose strict ancestors are all expandable;ℐmax\\mathcal\{I\}\_\{\\max\}denotes the set of candidate nodes\. Once the proposal atv\+v^\{\+\}is generated, the chain moves from a candidate nodevvtov\+v^\{\+\}if the proposal is accepted and tov−v^\{\-\}if it is rejected\.
- •*Ancestor\-closed\.*A setℐ⊆ℐmax\\mathcal\{I\}\\subseteq\\mathcal\{I\}\_\{\\max\}is ancestor\-closed if, for everyv∈ℐv\\in\\mathcal\{I\}, every strict ancestor ofvvalso lies inℐ\\mathcal\{I\}\.
- •*Selection\.*A selection is any ancestor\-closedℐ⊆ℐmax\\mathcal\{I\}\\subseteq\\mathcal\{I\}\_\{\\max\}; its elements are the expanded nodes\.
- •*Prefetched subtree\.*The rootv0v\_\{0\}together with both children of everyv∈ℐv\\in\\mathcal\{I\}\. Its internal nodes are exactly the nodes inℐ\\mathcal\{I\}, and its leaves are its nodes outsideℐ\\mathcal\{I\}; forℐ=∅\\mathcal\{I\}=\\varnothing, it consists ofv0v\_\{0\}alone, which is then its only leaf\.

Because a selection is ancestor\-closed, a selection of at mostNpfN\_\{\\mathrm\{pf\}\}nodes contains no node deeper thanNpf−1N\_\{\\mathrm\{pf\}\}\-1, so the depth cap is inactive whenK′≥NpfK^\{\\prime\}\\geq N\_\{\\mathrm\{pf\}\}\.

###### Definition 1\.

Fix a realization of the proposals and of their acceptance probabilities, withϵ∈\(0,12\)\\epsilon\\in\(0,\\tfrac\{1\}\{2\}\)as in Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3)\.

Rounded branch probabilities\.At each nodevv,

h⁡\(v\+,ϵ\)\\displaystyle h\(v^\{\+\};\\epsilon\):=\{0,A⁡\(v\+,v\)≤ϵ,1,A⁡\(v\+,v\)≥1−ϵ,A⁡\(v\+,v\),otherwise,\\displaystyle:=\\begin\{cases\}0,&A\(v^\{\+\},v\)\\leq\\epsilon,\\\\ 1,&A\(v^\{\+\},v\)\\geq 1\-\\epsilon,\\\\ A\(v^\{\+\},v\),&\\textup\{otherwise\},\\end\{cases\}\(10\)h⁡\(v−,ϵ\)\\displaystyle h\(v^\{\-\};\\epsilon\):=1−h⁡\(v\+,ϵ\)\.\\displaystyle:=1\-h\(v^\{\+\};\\epsilon\)\.Traversal\.Fix a setℐ\\mathcal\{I\}of nodes of𝒯K′\\mathcal\{T\}\_\{K^\{\\prime\}\}, for example a selection\. A traversal follows one child of each node ofℐ\\mathcal\{I\}that it reaches: from a reached nodev∈ℐv\\in\\mathcal\{I\}, it moves tov\+v^\{\+\}with probabilityh⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)and tov−v^\{\-\}with probabilityh⁡\(v−,ϵ\)h\(v^\{\-\};\\epsilon\), independently across nodes, and it stops at the first node outsideℐ\\mathcal\{I\}\. The traversal*completes a transition*at each node ofℐ\\mathcal\{I\}that it reaches, whichever child it then moves to\. WriteFℐ​\(v,ϵ\)F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)for the expected number of transitions completed by a traversal started atvv\.

Reaching weights\.The reaching weight of a node is the product of the branch probabilities along its path from the root:

R\(v0;ϵ\)=1,R\(v±;ϵ\)=R\(v;ϵ\)h\(v±;ϵ\)for every nodev\.R\(v\_\{0\};\\epsilon\)=1,\\qquad R\(v^\{\\pm\};\\epsilon\)=R\(v;\\epsilon\)\\,h\(v^\{\\pm\};\\epsilon\)\\quad\\textup\{for every node \}v\.\(11\)The traversal,FℐF\_\{\\mathcal\{I\}\}, andRRuse only branch probabilities in\[0,1\]\[0,1\]withh⁡\(v−,ϵ\)=1−h⁡\(v\+,ϵ\)h\(v^\{\-\};\\epsilon\)=1\-h\(v^\{\+\};\\epsilon\); the lemmas below therefore also hold for any such branch probabilities, in particular for the predictedh^\\widehat\{h\}of Appendix[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)\.

### C\.2The Transition\-Count Objective

Following prior prefetching analyses\([Strid, 2010](https://arxiv.org/html/2610.13171#bib.bib53)\), we score a selectionℐ\\mathcal\{I\}by the expected number of MH transitions it completes and by the number of requests it issues\. By Definition[1](https://arxiv.org/html/2610.13171#Thmdefinition1), a traversal completes one transition at each node ofℐ\\mathcal\{I\}that it visits, whether the proposal there is accepted or rejected\. Lemma[1](https://arxiv.org/html/2610.13171#Thmlemma1)writes the expected count from the root,Fℐ​\(v0,ϵ\)F\_\{\\mathcal\{I\}\}\(v\_\{0\};\\epsilon\), as a sum of reaching weights, and Lemma[2](https://arxiv.org/html/2610.13171#Thmlemma2)gives the recursive form used by the dynamic program\.

###### Lemma 1\(Expected transition count\)\.

For any ancestor\-closed setℐ\\mathcal\{I\}of nodes of𝒯K′\\mathcal\{T\}\_\{K^\{\\prime\}\}\(in particular, any selection\), with reaching weightsR⁡\(v,ϵ\)R\(v;\\epsilon\)as in \([11](https://arxiv.org/html/2610.13171#A3.E11)\),

Fℐ​\(v0,ϵ\)=∑v∈ℐR⁡\(v,ϵ\)\.F\_\{\\mathcal\{I\}\}\(v\_\{0\};\\epsilon\)=\\sum\_\{v\\in\\mathcal\{I\}\}R\(v;\\epsilon\)\.\(12\)

###### Proof\.

A traversal fromv0v\_\{0\}follows a single path, so it visits each node at most once, and its transition count equals the number of nodes inℐ\\mathcal\{I\}it visits\. By linearity of expectation,

Fℐ​\(v0,ϵ\)=∑v∈ℐP⁡\(the traversal visits​v\)\.F\_\{\\mathcal\{I\}\}\(v\_\{0\};\\epsilon\)=\\sum\_\{v\\in\\mathcal\{I\}\}P\(\\text\{the traversal visits \}v\)\.Fixv∈ℐv\\in\\mathcal\{I\}\. By ancestor closure, every strict ancestor ofvvlies inℐ\\mathcal\{I\}, so the traversal cannot stop on the path fromv0v\_\{0\}tovv\. It therefore visitsvvexactly when it takes every branch on that path, an event whose probability is the product of the branch probabilities along the path, that is,R⁡\(v,ϵ\)R\(v;\\epsilon\)by \([11](https://arxiv.org/html/2610.13171#A3.E11)\)\. Summing overv∈ℐv\\in\\mathcal\{I\}gives \([12](https://arxiv.org/html/2610.13171#A3.E12)\); forℐ=∅\\mathcal\{I\}=\\varnothing, both sides are zero\. ∎

###### Lemma 2\(Recursive form\)\.

For any setℐ\\mathcal\{I\}of nodes of𝒯K′\\mathcal\{T\}\_\{K^\{\\prime\}\},Fℐ​\(v,ϵ\)=0F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)=0forv∉ℐv\\notin\\mathcal\{I\}, and

Fℐ​\(v,ϵ\)\\displaystyle F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)=1\+h\(v\+;ϵ\)Fℐ\(v\+;ϵ\)\+h\(v−;ϵ\)Fℐ\(v−;ϵ\),v∈ℐ\.\\displaystyle=1\+h\(v^\{\+\};\\epsilon\)F\_\{\\mathcal\{I\}\}\(v^\{\+\};\\epsilon\)\+h\(v^\{\-\};\\epsilon\)F\_\{\\mathcal\{I\}\}\(v^\{\-\};\\epsilon\),\\qquad v\\in\\mathcal\{I\}\.\(13\)

vvv\+v^\{\+\}v−v^\{\-\}h⁡\(v\+,ϵ\)=0h\(v^\{\+\};\\epsilon\)=0h⁡\(v−,ϵ\)=1h\(v^\{\-\};\\epsilon\)=1✗ ✗ Fℐ​\(v−,ϵ\)F\_\{\\mathcal\{I\}\}\(v^\{\-\};\\epsilon\)\(a\)ϵ\\epsilon\-certain rejection

vvv\+v^\{\+\}v−v^\{\-\}h⁡\(v\+,ϵ\)=1h\(v^\{\+\};\\epsilon\)=1h⁡\(v−,ϵ\)=0h\(v^\{\-\};\\epsilon\)=0Fℐ​\(v\+,ϵ\)F\_\{\\mathcal\{I\}\}\(v^\{\+\};\\epsilon\)✗ ✗ \(b\)ϵ\\epsilon\-certain acceptance

vvv\+v^\{\+\}v−v^\{\-\}h⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)h⁡\(v−,ϵ\)h\(v^\{\-\};\\epsilon\)Fℐ​\(v\+,ϵ\)F\_\{\\mathcal\{I\}\}\(v^\{\+\};\\epsilon\)Fℐ​\(v−,ϵ\)F\_\{\\mathcal\{I\}\}\(v^\{\-\};\\epsilon\)\(c\)ϵ\\epsilon\-uncertain decision

Figure 9:Visualization of \([13](https://arxiv.org/html/2610.13171#A3.E13)\): \(a\) certain rejection, \(b\) certain acceptance, and \(c\) an uncertain rounded decision\. A✗marks a pruned edge\. The proposal atv\+v^\{\+\}is required in every case\.###### Proof\.

A traversal started atv∉ℐv\\notin\\mathcal\{I\}stops immediately and completes no transition\. A traversal started atv∈ℐv\\in\\mathcal\{I\}completes one transition atvvand, since the choices at different nodes are independent, then proceeds as a traversal started at the child it moves to\. By \([10](https://arxiv.org/html/2610.13171#A3.E10)\), the MH decision atvvfalls into one of three cases \(Figure[9](https://arxiv.org/html/2610.13171#A3.F9)\):

- •*Certain rejection*\(h⁡\(v\+,ϵ\)=0h\(v^\{\+\};\\epsilon\)=0, panel \(a\)\)\. The traversal moves tov−v^\{\-\}with probability one, soFℐ​\(v,ϵ\)=1\+Fℐ​\(v−,ϵ\)F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)=1\+F\_\{\\mathcal\{I\}\}\(v^\{\-\};\\epsilon\), which is \([13](https://arxiv.org/html/2610.13171#A3.E13)\) with a vanishingv\+v^\{\+\}term\.
- •*Certain acceptance*\(h⁡\(v\+,ϵ\)=1h\(v^\{\+\};\\epsilon\)=1, panel \(b\)\)\. The traversal moves tov\+v^\{\+\}with probability one, soFℐ​\(v,ϵ\)=1\+Fℐ​\(v\+,ϵ\)F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)=1\+F\_\{\\mathcal\{I\}\}\(v^\{\+\};\\epsilon\), which is \([13](https://arxiv.org/html/2610.13171#A3.E13)\) with a vanishingv−v^\{\-\}term\.
- •*Uncertain decision*\(0<h⁡\(v\+,ϵ\)<10<h\(v^\{\+\};\\epsilon\)<1, panel \(c\)\)\. The traversal moves tov\+v^\{\+\}with probabilityh⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)and tov−v^\{\-\}with probabilityh⁡\(v−,ϵ\)h\(v^\{\-\};\\epsilon\); conditioning on this outcome gives \([13](https://arxiv.org/html/2610.13171#A3.E13)\)\.

∎

Lemma[2](https://arxiv.org/html/2610.13171#Thmlemma2)is the basis of the dynamic program in Proposition[2](https://arxiv.org/html/2610.13171#Thmproposition2): by \([13](https://arxiv.org/html/2610.13171#A3.E13)\),Fℐ​\(v,ϵ\)F\_\{\\mathcal\{I\}\}\(v;\\epsilon\)depends onℐ\\mathcal\{I\}only through its parts belowv\+v^\{\+\}andv−v^\{\-\}, so an optimal selection belowvvcombines optimal selections below its two children\.

Remark\.The request count depends only onℐ\\mathcal\{I\}, not on the traversal: expanding a nodevvissues exactly one request, for the proposal atv\+v^\{\+\}, while the rejection childv−v^\{\-\}keeps the state ofvvand needs no proposal\. A selectionℐ\\mathcal\{I\}thus issues\|ℐ\|\|\\mathcal\{I\}\|requests and yields a prefetched subtree of2​\|ℐ\|\+12\|\\mathcal\{I\}\|\+1nodes\. Rounding does not lower this cost: at a certain rejection,h⁡\(v\+,ϵ\)=0h\(v^\{\+\};\\epsilon\)=0makes the acceptance branch unreachable, yet expandingvvstill costs the request for the proposal atv\+v^\{\+\}\. Rounding only prunes the low\-probability branch belowvv, so that no further requests are spent there\.

### C\.3Predictive Subtree Allocation

We want to expand the selectionℐ\\mathcal\{I\}that maximizes the expected transition countFℐ​\(v0,ϵ\)F\_\{\\mathcal\{I\}\}\(v\_\{0\};\\epsilon\)within the request budget\. This count depends on the branch probabilitiesh⁡\(v±,ϵ\)h\(v^\{\\pm\};\\epsilon\), which by \([10](https://arxiv.org/html/2610.13171#A3.E10)\) are determined by the acceptance probabilityA⁡\(v\+,v\)A\(v^\{\+\},v\)\. However,A⁡\(v\+,v\)A\(v^\{\+\},v\)is known only after the proposal atv\+v^\{\+\}has been generated and scored, so it is unavailable while we assemble the request batch\. We therefore use a classifier that, from information available before generation, predicts the probability that each candidate node is anϵ\\epsilon\-certain reject, anϵ\\epsilon\-certain accept, orϵ\\epsilon\-uncertain \(Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)reports its empirical results\)\. Below, we convert these class probabilities into predicted branch probabilitiesh^\\widehat\{h\}and formulate the allocation objective withh^\\widehat\{h\}in place ofhh\.

Notation\.Throughout this subsection,A:=A⁡\(v\+,v\)A:=A\(v^\{\+\},v\)denotes the acceptance probability of the proposal atv\+v^\{\+\}, viewed as a random variable, and conditioning onvvmeans conditioning on the information available before allocation\. As in Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3),vvis anϵ\\epsilon\-certain reject ifA≤ϵA\\leq\\epsilon, anϵ\\epsilon\-certain accept ifA≥1−ϵA\\geq 1\-\\epsilon, andϵ\\epsilon\-uncertain otherwise;P⁡\(v​isϵ\-certain reject\)P\(v\\text\{ is $\\epsilon$\-certain reject\}\)denotes the probability of this event given the information available before allocation, and similarly for the other two classes\.

Computingh^\\widehat\{h\}from the classifier\.For each candidate nodevv, the classifier takes the features ofvvthat are available before generation \(in our implementation, the cut fraction of the request atv\+v^\{\+\}\) and outputs, through a softmax \(Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)\), a predicted probability for each of the three classes rather than only the most likely class:

P^​\(v​isϵ\-certain reject\),P^​\(v​isϵ\-certain accept\),and\\displaystyle\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain reject\}\),\\qquad\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain accept\}\),\\qquad\\text\{and\}P^​\(v​isϵ\-uncertain\)=1−P^​\(v​isϵ\-certain reject\)−P^​\(v​isϵ\-certain accept\)\.\\displaystyle\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-uncertain\}\)=1\-\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain reject\}\)\-\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain accept\}\)\.We then compute the*predicted branch probabilities*as

h^​\(v\+,ϵ\)\\displaystyle\\widehat\{h\}\(v^\{\+\};\\epsilon\)=12​\[1\+P^​\(v​isϵ\-certain accept\)−P^​\(v​isϵ\-certain reject\)\],\\displaystyle=\\tfrac\{1\}\{2\}\\bigl\[1\+\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain accept\}\)\-\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain reject\}\)\\bigr\],\(14\)h^​\(v−,ϵ\)\\displaystyle\\widehat\{h\}\(v^\{\-\};\\epsilon\)=1−h^​\(v\+,ϵ\)\.\\displaystyle=1\-\\widehat\{h\}\(v^\{\+\};\\epsilon\)\.That is,h^​\(v\+,ϵ\)\\widehat\{h\}\(v^\{\+\};\\epsilon\)is the average of11\(certain accept\),00\(certain reject\), and12\\tfrac\{1\}\{2\}\(uncertain, the midpoint of\[ϵ,1−ϵ\]\[\\epsilon,1\-\\epsilon\]\), weighted by the predicted class probabilities; it is the valueh⋆​\(v\+,ϵ\)h^\{\\star\}\(v^\{\+\};\\epsilon\)of Lemma[3](https://arxiv.org/html/2610.13171#Thmlemma3)with the predicted class probabilities in place of the exact ones\.

###### Lemma 3\(Midpoint branch probability\)\.

Fix a nodevv\. Its exact class probabilities bound the mean rounded branch probability:

𝔼⁡\[h⁡\(v\+,ϵ\)∣v\]\\displaystyle\\mathbb\{E\}\[h\(v^\{\+\};\\epsilon\)\\mid v\]≥P⁡\(v​isϵ\-certain accept\)\+ϵ​P​\(v​isϵ\-uncertain\),\\displaystyle\\geq P\(v\\textup\{ is $\\epsilon$\-certain accept\}\)\+\\epsilon\\,P\(v\\textup\{ is $\\epsilon$\-uncertain\}\),\(15\)𝔼⁡\[h⁡\(v\+,ϵ\)∣v\]\\displaystyle\\mathbb\{E\}\[h\(v^\{\+\};\\epsilon\)\\mid v\]≤P⁡\(v​isϵ\-certain accept\)\+\(1−ϵ\)​P​\(v​isϵ\-uncertain\)\.\\displaystyle\\leq P\(v\\textup\{ is $\\epsilon$\-certain accept\}\)\+\(1\-\\epsilon\)\\,P\(v\\textup\{ is $\\epsilon$\-uncertain\}\)\.Define the*error*of a candidate valuex∈\[0,1\]x\\in\[0,1\]as\|x−𝔼⁡\[h⁡\(v\+,ϵ\)∣v\]\|\\bigl\|x\-\\mathbb\{E\}\[h\(v^\{\+\};\\epsilon\)\\mid v\]\\bigr\|, and its*worst\-case error*as the largest such error over all means allowed by \([15](https://arxiv.org/html/2610.13171#A3.E15)\)\. The worst\-case error is smallest at the midpoint of this interval,

h⋆​\(v\+,ϵ\)=12​\[1\+P⁡\(v​isϵ\-certain accept\)−P⁡\(v​isϵ\-certain reject\)\]\.h^\{\\star\}\(v^\{\+\};\\epsilon\)=\\tfrac\{1\}\{2\}\\bigl\[1\+P\(v\\textup\{ is $\\epsilon$\-certain accept\}\)\-P\(v\\textup\{ is $\\epsilon$\-certain reject\}\)\\bigr\]\.\(16\)

###### Proof\.

By \([10](https://arxiv.org/html/2610.13171#A3.E10)\),h⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)is11on the certain\-accept class,00on the certain\-reject class, andAAon the uncertain class, so

𝔼⁡\[h⁡\(v\+,ϵ\)∣v\]=P⁡\(v​isϵ\-certain accept\)\+P⁡\(v​isϵ\-uncertain\)​𝔼​\[A\|v​isϵ\-uncertain\]\.\\mathbb\{E\}\[h\(v^\{\+\};\\epsilon\)\\mid v\]=P\(v\\text\{ is $\\epsilon$\-certain accept\}\)\+P\(v\\text\{ is $\\epsilon$\-uncertain\}\)\\,\\mathbb\{E\}\\bigl\[A\\bigm\|v\\text\{ is $\\epsilon$\-uncertain\}\\bigr\]\.The conditional mean ofAAon the uncertain class lies in\[ϵ,1−ϵ\]\[\\epsilon,1\-\\epsilon\], which gives \([15](https://arxiv.org/html/2610.13171#A3.E15)\)\. For a quantity known only to lie in an interval\[a,b\]\[a,b\], an estimatexxhas worst\-case errormax⁡\{\|x−a\|,\|x−b\|\}≥\(b−a\)/2\\max\\\{\|x\-a\|,\|x\-b\|\\\}\\geq\(b\-a\)/2, with equality exactly atx=\(a\+b\)/2x=\(a\+b\)/2\. The midpoint of the interval in \([15](https://arxiv.org/html/2610.13171#A3.E15)\) is

P⁡\(v​isϵ\-certain accept\)\+12​P​\(v​isϵ\-uncertain\)\\displaystyle P\(v\\text\{ is $\\epsilon$\-certain accept\}\)\+\\tfrac\{1\}\{2\}\\,P\(v\\text\{ is $\\epsilon$\-uncertain\}\)=12​\[1\+P⁡\(v​isϵ\-certain accept\)−P⁡\(v​isϵ\-certain reject\)\],\\displaystyle=\\tfrac\{1\}\{2\}\\bigl\[1\+P\(v\\text\{ is $\\epsilon$\-certain accept\}\)\-P\(v\\text\{ is $\\epsilon$\-certain reject\}\)\\bigr\],where the equality uses that the three class probabilities sum to one\. This is \([16](https://arxiv.org/html/2610.13171#A3.E16)\)\. ∎

Objective formulation\.Withh^\\widehat\{h\}in place ofhh, Lemma[1](https://arxiv.org/html/2610.13171#Thmlemma1)gives the allocation objective: choose the selectionℐ\\mathcal\{I\}that maximizes the predicted expected transition count within the request budget,

maxℐ\\displaystyle\\max\_\{\\mathcal\{I\}\}F^ℐ​\(v0,ϵ\)=∑v∈ℐR^​\(v,ϵ\)\\displaystyle\\widehat\{F\}\_\{\\mathcal\{I\}\}\(v\_\{0\};\\epsilon\)=\\sum\_\{v\\in\\mathcal\{I\}\}\\widehat\{R\}\(v;\\epsilon\)\(17\)s\.t\.\\displaystyle\\text\{s\.t\.\}ℐ⊆ℐmax​ancestor\-closed,\\displaystyle\\mathcal\{I\}\\subseteq\\mathcal\{I\}\_\{\\max\}\\ \\text\{ancestor\-closed\},\|ℐ\|≤Npf,\\displaystyle\|\\mathcal\{I\}\|\\leq N\_\{\\mathrm\{pf\}\},where

- •R^\\widehat\{R\}andF^\\widehat\{F\}are the reaching weights and the expected transition count of Definition[1](https://arxiv.org/html/2610.13171#Thmdefinition1), computed with the predicted branch probabilitiesh^\\widehat\{h\}in \([14](https://arxiv.org/html/2610.13171#A3.E14)\) in place of the unknownhh;
- •the candidate setℐmax\\mathcal\{I\}\_\{\\max\}, determined by Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1)and the depth capK′K^\{\\prime\}, ensures that every selected request can be generated in a single batch;
- •ancestor closure requires every ancestor of a selected node to be selected as well\.

A node withR^​\(v,ϵ\)=0\\widehat\{R\}\(v;\\epsilon\)=0would contribute nothing to the objective but still cost a request; this requires someh^\\widehat\{h\}on its path to be exactly00or11, which our softmax classifier never outputs, since all three of its class probabilities are positive\.

Why rounded estimates\.The exact countFℐ​\(v0,0\)F\_\{\\mathcal\{I\}\}\(v\_\{0\};0\)requires the value ofAA, which is unknown until the proposal is generated, and an estimate ofAAitself would carry error at every decision\. Rounding removes the need to estimateAAon theϵ\\epsilon\-certain decisions, at a bias of at mostϵ\\epsilonper branch probability, but it does not remove the error of the class probabilities themselves\. On theϵ\\epsilon\-certain decisions,h⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)is exactly00or11and is determined by the class alone; on theϵ\\epsilon\-uncertain ones, given exact class probabilities, the midpoint estimate is off by at most12​\(1−2​ϵ\)​P​\(v​isϵ\-uncertain\)\\tfrac\{1\}\{2\}\(1\-2\\epsilon\)\\,P\(v\\text\{ is $\\epsilon$\-uncertain\}\)\(Lemma[3](https://arxiv.org/html/2610.13171#Thmlemma3)\)\. Since only5%5\\%–33%33\\%of decisions areϵ\\epsilon\-uncertain \(Figure[4](https://arxiv.org/html/2610.13171#S3.F4)\), the midpoint error affects a minority of decisions; the error of the classifier adds to it on every decision\.

### C\.4Optimal Budget Allocation via Dynamic Programming

DefineV⁡\(v,b,ϵ\)V\(v,b;\\epsilon\)as the largest predicted transition count attainable fromvvwith at mostbbrequests,

V⁡\(v,b,ϵ\)=maxℐv​feasible below​v,\|ℐv\|≤b⁡F^ℐv​\(v,ϵ\),V\(v,b;\\epsilon\)=\\max\_\{\\begin\{subarray\}\{c\}\\mathcal\{I\}\_\{v\}\\text\{ feasible below \}v,\\\\ \|\\mathcal\{I\}\_\{v\}\|\\leq b\\end\{subarray\}\}\\widehat\{F\}\_\{\\mathcal\{I\}\_\{v\}\}\(v;\\epsilon\),\(18\)where a set of candidate nodesℐv\\mathcal\{I\}\_\{v\}is*feasible belowvv*ifℐv⊆ℐmax\\mathcal\{I\}\_\{v\}\\subseteq\\mathcal\{I\}\_\{\\max\}, every element ofℐv\\mathcal\{I\}\_\{v\}lies in the subtree rooted atvv, and every candidate node on the path fromvvto an element ofℐv\\mathcal\{I\}\_\{v\}also lies inℐv\\mathcal\{I\}\_\{v\}\.

The optimization in \([18](https://arxiv.org/html/2610.13171#A3.E18)\) decomposes the budget at each node: one request expandsvvitself, and the remainingb−1b\-1are split between its two child subtrees before the outcome atvvis known \(Figure[10](https://arxiv.org/html/2610.13171#A3.F10)\)\. This decomposition is inspired by the tree\-based speculative decoding of Sequoia\([Chen et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib12)\)\.

###### Proposition 2\(Optimal predictive allocation\)\.

Fixϵ\\epsilonand the predicted branch probabilitiesh^​\(v\+,ϵ\)\\widehat\{h\}\(v^\{\+\};\\epsilon\)andh^​\(v−,ϵ\)\\widehat\{h\}\(v^\{\-\};\\epsilon\)in \([14](https://arxiv.org/html/2610.13171#A3.E14)\)\. For every nodevvand every budgetb≥0b\\geq 0,

V⁡\(v,b,ϵ\)=\{0,if​v∉ℐmax,0,if​b=0,1\+max0≤m≤b−1⁡\{h^​\(v\+,ϵ\)​V​\(v\+,m,ϵ\)\+h^​\(v−,ϵ\)​V​\(v−,b−1−m,ϵ\)\},otherwise\.V\(v,b;\\epsilon\)=\\begin\{cases\}0,&\\textup\{if \}v\\notin\\mathcal\{I\}\_\{\\max\},\\\\\[2\.0pt\] 0,&\\textup\{if \}b=0,\\\\\[2\.0pt\] 1\+\\max\\limits\_\{0\\leq m\\leq b\-1\}\\big\\\{\\widehat\{h\}\(v^\{\+\};\\epsilon\)V\(v^\{\+\},m;\\epsilon\)\+\\widehat\{h\}\(v^\{\-\};\\epsilon\)V\(v^\{\-\},b\-1\-m;\\epsilon\)\\big\\\},&\\textup\{otherwise\}\.\\end\{cases\}\(19\)The maximum in \([17](https://arxiv.org/html/2610.13171#A3.E17)\) equalsV⁡\(v0,Npf,ϵ\)V\(v\_\{0\},N\_\{\\mathrm\{pf\}\};\\epsilon\)\.

vvone requestnnavailable requestsv\+v^\{\+\}v−v^\{\-\}accept with predictedprobabilityh^​\(v\+,ϵ\)\\widehat\{h\}\(v^\{\+\};\\epsilon\)reject with predictedprobabilityh^​\(v−,ϵ\)\\widehat\{h\}\(v^\{\-\};\\epsilon\)left subtreeright subtreemmcontinuation requestsn−1−mn\-1\-mcontinuation requestsFigure 10:Budget decomposition visualization for Proposition[2](https://arxiv.org/html/2610.13171#Thmproposition2)\.###### Proof\.

*Boundary cases\.*A nonempty selection feasible belowvvcontainsvv, so it needs bothv∈ℐmaxv\\in\\mathcal\{I\}\_\{\\max\}andb≥1b\\geq 1\. Either boundary case therefore leaves only the empty selection, givingV⁡\(v,b,ϵ\)=0V\(v,b;\\epsilon\)=0\. Fixv∈ℐmaxv\\in\\mathcal\{I\}\_\{\\max\}andb≥1b\\geq 1below\.

*Upper bound\.*Expandingvvalone has value one by Lemma[2](https://arxiv.org/html/2610.13171#Thmlemma2), so an optimalℐv\\mathcal\{I\}\_\{v\}is nonempty and hence containsvv, which costs one request\. Its remaining nodes lie in the two child subtrees, and its restriction to each subtree is feasible below that child\. Ifmmof them lie belowv\+v^\{\+\}and at mostb−1−mb\-1\-mbelowv−v^\{\-\}, where0≤m≤b−10\\leq m\\leq b\-1, then Lemma[2](https://arxiv.org/html/2610.13171#Thmlemma2)withh^\\widehat\{h\}in place ofhhand the optimality of each child value give

F^ℐv​\(v,ϵ\)≤1\+h^​\(v\+,ϵ\)​V​\(v\+,m,ϵ\)\+h^​\(v−,ϵ\)​V​\(v−,b−1−m,ϵ\)\.\\widehat\{F\}\_\{\\mathcal\{I\}\_\{v\}\}\(v;\\epsilon\)\\leq 1\+\\widehat\{h\}\(v^\{\+\};\\epsilon\)V\(v^\{\+\},m;\\epsilon\)\+\\widehat\{h\}\(v^\{\-\};\\epsilon\)V\(v^\{\-\},b\-1\-m;\\epsilon\)\.Maximizing overmmgives the upper bound in \([19](https://arxiv.org/html/2610.13171#A3.E19)\)\.

*Attainability\.*Conversely, combine a maximizingmmwith optimal selections belowv\+v^\{\+\}andv−v^\{\-\}at capacitiesmmandb−1−mb\-1\-m\. Together with the expansion ofvvthey are feasible belowvvand use at mostbbrequests, and Lemma[2](https://arxiv.org/html/2610.13171#Thmlemma2)gives them exactly the maximized value\. The bound is attained, which proves \([19](https://arxiv.org/html/2610.13171#A3.E19)\); induction from the leaves of the finite tree𝒯K′\\mathcal\{T\}\_\{K^\{\\prime\}\}then determines everyV⁡\(v,b,ϵ\)V\(v,b;\\epsilon\)\.

Finally, feasibility belowv0v\_\{0\}is ancestor closure withinℐmax\\mathcal\{I\}\_\{\\max\}, soV⁡\(v0,Npf,ϵ\)V\(v\_\{0\},N\_\{\\mathrm\{pf\}\};\\epsilon\)is the optimum of \([17](https://arxiv.org/html/2610.13171#A3.E17)\)\. ∎

Remark\.Proposition[2](https://arxiv.org/html/2610.13171#Thmproposition2)requires the predicted branch probabilitiesh^\\widehat\{h\}at every candidate node\. Estimating them reduces to classification \(Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)\): by \([10](https://arxiv.org/html/2610.13171#A3.E10)\),h⁡\(v\+,ϵ\)h\(v^\{\+\};\\epsilon\)is exactly zero or one on the twoϵ\\epsilon\-certain classes, so a classifier only needs to predict the class probabilities of each candidate node, and Lemma[3](https://arxiv.org/html/2610.13171#Thmlemma3)converts them intoh^​\(v\+,ϵ\)\\widehat\{h\}\(v^\{\+\};\\epsilon\)without modelingAAwithin the uncertain class\.

## Appendix DExperimental Settings

### D\.1Baselines, Datasets, and Base LLMs

MH\-based samplers\.We apply PreSTO to three MH\-based samplers that target the same power distribution, and compare each sampler with its PreSTO variant:

- •PowerMH\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)builds a continuation block by block\. At each block, it extends the current prefix with the proposal LLM and then runs several MH updates that target the power\-sharpened distribution over the extended prefix\. Each update draws a cut position uniformly at random, keeps the tokens before it, resamples the suffix from the proposal LLM, and accepts or rejects the candidate with the MH correction\.
- •EntropyCut\([Zhou et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib62)\)modifies PowerMH by choosing cut positions where the base model’s next\-token entropy increases; these entropy jumps serve as a proxy for consequential reasoning decisions\. It regenerates the suffix from the chosen position and applies the MH correction, so the power target is preserved\.
- •MultiTryMHreplaces each single\-proposal PowerMH update with a Multiple\-Try Metropolis update\([Liu et al\., 2000](https://arxiv.org/html/2610.13171#bib.bib37)\)\. We use a simplified version of Entropy\-Guided Power Sampling \(EGPS\)\([Guo et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib19)\), namely the “EGPS \(MultiTryMH, with random pos\)” variant in their Figure 3: we omit entropy\-guided cut selection and draw the cut position uniformly at random\. This baseline preserves the power target while considering several candidate suffixes in each MH transition\.

Table 3:Datasets and their full sizes; every run uses only the first 20 prompts of each dataset\.CategoryDatasetSource \(Hugging Face\)InstancesMathematical reasoningMATH500[HuggingFaceH4/MATH\-500](https://huggingface.co/datasets/HuggingFaceH4/MATH-500)500AIME 24&25[Maxwell\-Jia/AIME\_2024](https://huggingface.co/datasets/Maxwell-Jia/AIME_2024)[MathArena/aime\_2025](https://huggingface.co/datasets/MathArena/aime_2025)45Code generationHumanEval[openai/openai\_humaneval](https://huggingface.co/datasets/openai/openai_humaneval)164MBPP[google\-research\-datasets/mbpp](https://huggingface.co/datasets/google-research-datasets/mbpp)257LCB V6[livecodebench/code\_generation\_lite](https://huggingface.co/datasets/livecodebench/code_generation_lite)175Scientific and general knowledgeGPQA[Idavidrein/gpqa](https://huggingface.co/datasets/Idavidrein/gpqa)198MMLU[cais/mmlu](https://huggingface.co/datasets/cais/mmlu)14,042Datasets\.We evaluate on seven datasets in three task categories \(Table[3](https://arxiv.org/html/2610.13171#A4.T3)\): mathematical reasoning \(MATH500\([Lightman et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib36)\), a 500\-problem subset of MATH\([Hendrycks et al\., 2021b](https://arxiv.org/html/2610.13171#bib.bib24)\), and AIME 24&25\), code generation \(HumanEval\([Chen et al\., 2021](https://arxiv.org/html/2610.13171#bib.bib10)\), MBPP\([Austin et al\., 2021](https://arxiv.org/html/2610.13171#bib.bib4)\), and LiveCodeBench V6 \(LCB V6\)\([Jain et al\., 2025](https://arxiv.org/html/2610.13171#bib.bib26)\)\), and scientific and general knowledge \(GPQA Diamond \(GPQA\)\([Rein et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib45)\)and MMLU\([Hendrycks et al\., 2021a](https://arxiv.org/html/2610.13171#bib.bib23)\)\)\.

Table 4:Base LLMs and their sources\.FamilyBase LLMSource \(Hugging Face\)ReleasedQwen3Qwen3\-4B[Qwen/Qwen3\-4B](https://huggingface.co/Qwen/Qwen3-4B)Apr 2025Qwen3\-8B[Qwen/Qwen3\-8B](https://huggingface.co/Qwen/Qwen3-8B)Apr 2025Qwen3\.5Qwen3\.5\-4B[Qwen/Qwen3\.5\-4B](https://huggingface.co/Qwen/Qwen3.5-4B)Feb 2026Qwen3\.5\-9B[Qwen/Qwen3\.5\-9B](https://huggingface.co/Qwen/Qwen3.5-9B)Feb 2026Gemma4Gemma4\-12B\-it[google/gemma\-4\-12B\-it](https://huggingface.co/google/gemma-4-12B-it)May 2026Base LLMs\.We evaluate five base LLMs \(Table[4](https://arxiv.org/html/2610.13171#A4.T4)\), where “base LLM” denotes the backbonep0p\_\{0\}\. Each is a recent open\-weight release from a widely adopted model family: two parameter scales from each of the Qwen3 and Qwen3\.5 generations, and the larger Gemma4\-12B\-it, so the models span 4B to 12B parameters\. None is a pretrained\-only checkpoint: the four Qwen models are the default releases rather than the\-Basevariants and ship with chat templates that support a thinking mode, and Gemma4\-12B\-it is instruction\-tuned\.

### D\.2Evaluation Metrics

Execution Efficiencymeasures the cost of running the same MH sampler for a fixed number of transitions\.

- •MH transitions per model call\.The number of MH transitions realized per model call; higher means more chain progress per call\. On each prompt, a method that completesKKrealized MH transitions realizesK/\#​of​model​callsK/\\mathrm\{\\\#\\ of\\ model\\ calls\}transitions per call\.
- •Wall\-clock time and speedup\.We record the wall\-clock time of every model call\. On each prompt, a method’stime​per​call\\mathrm\{time\\ per\\ call\}is the mean duration of its timed model calls, andcall​time=\#​of​model​calls×time​per​call\\mathrm\{call\\ time\}=\\mathrm\{\\\#\\ of\\ model\\ calls\}\\times\\mathrm\{time\\ per\\ call\}is its cumulative model\-call time\. Every reported speedup is a ratio of means over the promptsi=1,…,Ni=1,\\ldots,N: the mean cumulative model\-call time of the sequential sampler divided by that of its PreSTO variant, Speedup=1N​∑icall​timei​\(sampler\)1N​∑icall​timei​\(PreSTO variant\)\.\\operatorname\{Speedup\}=\\frac\{\\frac\{1\}\{N\}\\sum\_\{i\}\\mathrm\{call\\ time\}\_\{i\}\(\\text\{sampler\}\)\}\{\\frac\{1\}\{N\}\\sum\_\{i\}\\mathrm\{call\\ time\}\_\{i\}\(\\text\{\{PreSTO\} variant\}\)\}\.\(20\)We decompose it with ratios of means as well: the*increase in time per call*is the mean time per call of the PreSTO variant divided by that of the sampler, and the*reduction in model calls*is the speedup multiplied by this increase, so that the speedup equals the reduction in calls divided by the increase in time per call \(Figure[1](https://arxiv.org/html/2610.13171#S1.F1)\)\.

Sample Qualitymeasures whether PreSTO changes the samples after the same number of transitions\.

- •Likelihood and confidence\.Prior work evaluates MCMC samplers for text by comparing their sampled distributions with reference distributions\([Forristal et al\., 2023](https://arxiv.org/html/2610.13171#bib.bib17);[Du et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib13)\)\. For power sharpening,[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28)characterize sampled responses by their length\-normalized base\-model likelihood and confidence\. Let𝐱0:n\(K\)=\(𝐱0,𝐱1:n\(K\)\)\\mathbf\{x\}^\{\(K\)\}\_\{0:n\}=\(\\mathbf\{x\}\_\{0\},\\mathbf\{x\}^\{\(K\)\}\_\{1:n\}\)be the terminal state after exactlyKKrealized MH transitions: the prompt𝐱0\\mathbf\{x\}\_\{0\}followed by a response of lengthnn\. Its length\-normalized log\-likelihood is Log−Likelihood\(𝐱\(K\)\)=1nlogp0\(𝐱1:n\(K\)∣𝐱0\),\\operatorname\{Log\-Likelihood\}\(\\mathbf\{x\}^\{\(K\)\}\)=\\frac\{1\}\{n\}\\log p\_\{0\}\(\\mathbf\{x\}^\{\(K\)\}\_\{1:n\}\\mid\\mathbf\{x\}\_\{0\}\),\(21\)and its confidence is the mean negative entropy of the base model’s next\-token distributions along the sequence: Confidence\(𝐱\(K\)\)=1n∑t=1n∑u∈𝒱p0\(u∣𝐱0:t−1\(K\)\)logp0\(u∣𝐱0:t−1\(K\)\),\\operatorname\{Confidence\}\(\\mathbf\{x\}^\{\(K\)\}\)=\\frac\{1\}\{n\}\\sum\_\{t=1\}^\{n\}\\sum\_\{u\\in\\mathcal\{V\}\}p\_\{0\}\(u\\mid\\mathbf\{x\}^\{\(K\)\}\_\{0:t\-1\}\)\\log p\_\{0\}\(u\\mid\\mathbf\{x\}^\{\(K\)\}\_\{0:t\-1\}\),\(22\)where𝒱\\mathcal\{V\}is the vocabulary\. Both statistics are computed under the same base modelp0p\_\{0\}, so they are comparable across samplers\. Higher log\-likelihood means a higher mean token log\-probability underp0p\_\{0\}, and higher confidence means lower predictive uncertainty along the sequence\.
- •Paired TOST equivalence test\.This test checks whether PreSTO changes the mean of each statistic by less than a small marginδ\\delta\. For each sampler and its PreSTO variant, we match prompts and seeds, run both for the sameKK, and take the per\-prompt differencedid\_\{i\}of each statistic \(PreSTO variant minus sequential sampler\), with meanμd\\mu\_\{d\}\. The two one\-sided tests \(TOST\) procedure\([Schuirmann, 1987](https://arxiv.org/html/2610.13171#bib.bib48);[Lakens, 2017](https://arxiv.org/html/2610.13171#bib.bib30)\)tests H0:\|μd\|≥δagainstH1:\|μd\|<δH\_\{0\}:\|\\mu\_\{d\}\|\\geq\\delta\\qquad\\text\{against\}\\qquad H\_\{1\}:\|\\mu\_\{d\}\|<\\delta\(23\)with two one\-sided pairedtt\-tests;peqp\_\{\\mathrm\{eq\}\}is the larger of their twopp\-values\. We setδ\\deltato 0\.2 standard deviations of the statistic across prompts under the sequential sampler, a conventional small effect, and declare equivalence whenpeq<0\.05p\_\{\\mathrm\{eq\}\}<0\.05, that is, when the 90% confidence interval forμd\\mu\_\{d\}lies within\(−δ,δ\)\(\-\\delta,\\delta\)\.

Hardware\-Resource Efficiencymeasures how much of the KV\-cache pool a sampler occupies and how much prefix computation it reuses\.

- •Peak KV\-pool use\.We report the peak fraction of occupied blocks in the pool, where higher use indicates greater cache demand\.
- •Prefix\-cache hit rate\.We measure prefix reuse as the cumulative token hit rate: the fraction of queried prefix tokens whose KV states are already cached\. A higher hit rate indicates greater reuse of prefix computation\.
- •Prefix\-cache miss tokens per transition\.We divide the number of prefix\-cache miss tokens by the number of realized MH transitions\. This complements the hit rate by measuring the absolute uncached workload per transition\.

### D\.3Implementation Environment

Table[5](https://arxiv.org/html/2610.13171#A4.T5)summarizes the experimental software and hardware environment\. We implement PowerMH, EntropyCut, MultiTryMH, and their PreSTO variants on top of vLLM, using custom engine patches\. For Case Study 6 \(Appendix[E\.6](https://arxiv.org/html/2610.13171#A5.SS6)\), we also implement PowerMH and PreSTO\-PowerMH on SGLang\.

vLLM engine patches\.Each MH transition needs the log\-probability of a proposed suffix under both the proposalqτq\_\{\\tau\}and the base modelp0p\_\{0\}, and EntropyCut also needs the next\-token entropy ofp0p\_\{0\}at every position\. The unmodified vLLM engine returns log\-probabilities from only one version of the logits, either before or after temperature scaling; this choice is an engine\-wide setting \(logprobs\_mode\), not a per\-request option\. We therefore patch the vLLM V1 engine, run withlogprobs\_mode=processed\_logprobs, to return all of these quantities from the forward pass that generates each token\.

Before temperature scaling, penalties, or any other logit processing, the patched sampler keeps a float32 copy of the logits\. For each sampled tokenxtx\_\{t\}, it returns \(i\) the proposal log\-probabilitylogqτ\(xt∣𝐱0:t−1\)\\log q\_\{\\tau\}\(x\_\{t\}\\mid\\mathbf\{x\}\_\{0:t\-1\}\)from the processed logits, as in unmodified vLLM; \(ii\) the base\-model log\-probabilitylogp0\(xt∣𝐱0:t−1\)\\log p\_\{0\}\(x\_\{t\}\\mid\\mathbf\{x\}\_\{0:t\-1\}\)from the unprocessed copy; and \(iii\) the full\-vocabulary entropy ofp0p\_\{0\}, computed from the unprocessed copy with the natural logarithm,

Ht=−∑u∈𝒱p0\(u∣𝐱0:t−1\)logp0\(u∣𝐱0:t−1\),H\_\{t\}=\-\\sum\_\{u\\in\\mathcal\{V\}\}p\_\{0\}\(u\\mid\\mathbf\{x\}\_\{0:t\-1\}\)\\log p\_\{0\}\(u\\mid\\mathbf\{x\}\_\{0:t\-1\}\),

### D\.4Hyperparameter Configurations

Table[6](https://arxiv.org/html/2610.13171#A4.T6)lists the default power\-sampling settings and the settings of our case studies\. Following[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28), we set the proposal temperature toτ=1/α\\tau=1/\\alphafor every sampler except MultiTryMH and PreSTO\-MultiTryMH, whose candidates use the temperatures in Table[6](https://arxiv.org/html/2610.13171#A4.T6)\(a\); all runs use seed 10086\.

Table 5:Software and hardware configuration\.SoftwareVersion / configurationPython3\.13\.0PyTorch2\.13\.0vLLM0\.27\.1 \(V1 engine\) with custom engine patchesTransformers5\.14\.1\(a\)Software configurationHardwareSpecificationGPU1×\\timesNVIDIA H100 96 GB \(GH200 Grace Hopper Superchip\)CPUNVIDIA Grace CPU, 72 cores \(3\.456 GHz\)Memory480 GB LPDDR5X unified memory\(b\)Hardware configurationTable 6:Hyperparameter configurations\.ParameterSettingResponse lengthn=1024n=1024tokens \(fixed; no early stop at EOS\)Block sizea single block,B=n=1024B=n=1024Power exponentα=4\.0\\alpha=4\.0Proposal LLMqτ=q\_\{\\tau\}=base model sampled at temperatureτ\\tauProposal temperatureτ=1/α=0\.25\\tau=1/\\alpha=0\.25Realized MH transitionsK=100K=100Prompts per datasetfirst 20 promptsSeed10086Traversal ruledefault BFSPrefetch budgetNpf=20N\_\{\\mathrm\{pf\}\}=20EntropyCut cut\-law exponentβ=4\.0\\beta=4\.0\(dimensionless\)MultiTryMH candidates per transition4, each at a temperature drawn from\{0\.25,0\.5,1\.0\}\\\{0\.25,0\.5,1\.0\\\}\(a\)Default power\-sampling configurationParameterSettingBase model and datasetp0=p\_\{0\}=Qwen3\.5\-9B on LCB \(Case Studies 1, 2, 5–8\)Realized MH transitionsK∈\{10,20,30\}K\\in\\\{10,20,30\\\}\(Case Study 8\)Certainty thresholdϵ=0\.01\\epsilon=0\.01\(Case Studies 4, 5, 7\)Prefetch budget \(Case Study 2,5\)Npf∈\{8,10,12,16,20\}N\_\{\\mathrm\{pf\}\}\\in\\\{8,10,12,16,20\\\}\(b\)Case study configuration

## Appendix EAdditional Experimental Results

### E\.1Full results: Acceleration across base LLMs and datasets

We pair PowerMH, EntropyCut, and MultiTryMH with their PreSTO variants on all five base LLMs and seven datasets\. Tables[7](https://arxiv.org/html/2610.13171#A5.T7),[8](https://arxiv.org/html/2610.13171#A5.T8), and[9](https://arxiv.org/html/2610.13171#A5.T9)report the mean and standard deviation of each metric for the three samplers\.

Table 7:PowerMH execution metrics across base LLMs\.DatasetBase LLMTotal Time \(s\)↓\\downarrowTransitionsper call↑\\uparrowTime/call \(s\)↓\\downarrowSpeedupMATH500\(Fig\.[11](https://arxiv.org/html/2610.13171#A5.F11)\)Qwen3\-4B327\.83±20\.11/155\.68±21\.84327\.83\_\{\\pm 20\.11\}/155\.68\_\{\\pm 21\.84\}1/4\.42±0\.601/4\.42\_\{\\pm 0\.60\}3\.28±0\.20/6\.77±0\.093\.28\_\{\\pm 0\.20\}/6\.77\_\{\\pm 0\.09\}2\.11×2\.11\\timesQwen3\-8B448\.28±27\.52/200\.65±31\.21448\.28\_\{\\pm 27\.52\}/200\.65\_\{\\pm 31\.21\}1/4\.37±0\.681/4\.37\_\{\\pm 0\.68\}4\.48±0\.28/8\.58±0\.144\.48\_\{\\pm 0\.28\}/8\.58\_\{\\pm 0\.14\}2\.23×2\.23\\timesQwen3\.5\-4B371\.97±22\.70/249\.10±70\.00371\.97\_\{\\pm 22\.70\}/249\.10\_\{\\pm 70\.00\}1/3\.57±0\.991/3\.57\_\{\\pm 0\.99\}3\.72±0\.23/8\.29±0\.113\.72\_\{\\pm 0\.23\}/8\.29\_\{\\pm 0\.11\}1\.49×1\.49\\timesQwen3\.5\-9B499\.24±30\.53/242\.93±45\.34499\.24\_\{\\pm 30\.53\}/242\.93\_\{\\pm 45\.34\}1/4\.50±0\.751/4\.50\_\{\\pm 0\.75\}4\.99±0\.31/10\.63±0\.204\.99\_\{\\pm 0\.31\}/10\.63\_\{\\pm 0\.20\}2\.06×2\.06\\timesGemma4\-12B\-it687\.48±41\.01/395\.55±77\.86687\.48\_\{\\pm 41\.01\}/395\.55\_\{\\pm 77\.86\}1/3\.96±0\.681/3\.96\_\{\\pm 0\.68\}6\.87±0\.41/15\.21±0\.296\.87\_\{\\pm 0\.41\}/15\.21\_\{\\pm 0\.29\}1\.74×1\.74\\timesAIME 24&25Qwen3\-4B318\.76±19\.59/150\.66±32\.25318\.76\_\{\\pm 19\.59\}/150\.66\_\{\\pm 32\.25\}1/4\.66±0\.861/4\.66\_\{\\pm 0\.86\}3\.19±0\.20/6\.78±0\.113\.19\_\{\\pm 0\.20\}/6\.78\_\{\\pm 0\.11\}2\.12×2\.12\\timesQwen3\-8B447\.87±27\.50/195\.48±34\.63447\.87\_\{\\pm 27\.50\}/195\.48\_\{\\pm 34\.63\}1/4\.48±0\.711/4\.48\_\{\\pm 0\.71\}4\.48±0\.28/8\.53±0\.154\.48\_\{\\pm 0\.28\}/8\.53\_\{\\pm 0\.15\}2\.29×2\.29\\timesQwen3\.5\-4B360\.89±22\.43/217\.57±37\.98360\.89\_\{\\pm 22\.43\}/217\.57\_\{\\pm 37\.98\}1/3\.99±0\.621/3\.99\_\{\\pm 0\.62\}3\.61±0\.22/8\.47±0\.163\.61\_\{\\pm 0\.22\}/8\.47\_\{\\pm 0\.16\}1\.66×1\.66\\timesQwen3\.5\-9B498\.37±30\.48/239\.31±44\.47498\.37\_\{\\pm 30\.48\}/239\.31\_\{\\pm 44\.47\}1/4\.56±0\.721/4\.56\_\{\\pm 0\.72\}4\.98±0\.30/10\.63±0\.314\.98\_\{\\pm 0\.30\}/10\.63\_\{\\pm 0\.31\}2\.08×2\.08\\timesGemma4\-12B\-it686\.87±38\.96/389\.43±57\.27686\.87\_\{\\pm 38\.96\}/389\.43\_\{\\pm 57\.27\}1/3\.93±0\.531/3\.93\_\{\\pm 0\.53\}6\.87±0\.39/15\.04±0\.236\.87\_\{\\pm 0\.39\}/15\.04\_\{\\pm 0\.23\}1\.76×1\.76\\timesMBPPQwen3\-4B327\.45±20\.07/296\.53±65\.99327\.45\_\{\\pm 20\.07\}/296\.53\_\{\\pm 65\.99\}1/2\.42±0\.651/2\.42\_\{\\pm 0\.65\}3\.27±0\.20/6\.81±0\.083\.27\_\{\\pm 0\.20\}/6\.81\_\{\\pm 0\.08\}1\.10×1\.10\\timesQwen3\-8B447\.85±27\.46/446\.25±41\.30447\.85\_\{\\pm 27\.46\}/446\.25\_\{\\pm 41\.30\}1/1\.96±0\.191/1\.96\_\{\\pm 0\.19\}4\.48±0\.27/8\.68±0\.074\.48\_\{\\pm 0\.27\}/8\.68\_\{\\pm 0\.07\}1\.00×1\.00\\timesQwen3\.5\-4B370\.03±22\.56/221\.28±69\.63370\.03\_\{\\pm 22\.56\}/221\.28\_\{\\pm 69\.63\}1/4\.13±0\.941/4\.13\_\{\\pm 0\.94\}3\.70±0\.23/8\.56±0\.303\.70\_\{\\pm 0\.23\}/8\.56\_\{\\pm 0\.30\}1\.67×1\.67\\timesQwen3\.5\-9B497\.47±30\.41/309\.52±88\.73497\.47\_\{\\pm 30\.41\}/309\.52\_\{\\pm 88\.73\}1/3\.74±0\.841/3\.74\_\{\\pm 0\.84\}4\.97±0\.30/10\.92±0\.324\.97\_\{\\pm 0\.30\}/10\.92\_\{\\pm 0\.32\}1\.61×1\.61\\timesGemma4\-12B\-it684\.80±38\.84/475\.98±177\.87684\.80\_\{\\pm 38\.84\}/475\.98\_\{\\pm 177\.87\}1/3\.64±1\.291/3\.64\_\{\\pm 1\.29\}6\.85±0\.39/15\.29±0\.156\.85\_\{\\pm 0\.39\}/15\.29\_\{\\pm 0\.15\}1\.44×1\.44\\timesGPQAQwen3\-4B323\.68±21\.46/198\.61±42\.79323\.68\_\{\\pm 21\.46\}/198\.61\_\{\\pm 42\.79\}1/3\.55±0\.591/3\.55\_\{\\pm 0\.59\}3\.24±0\.21/6\.83±0\.083\.24\_\{\\pm 0\.21\}/6\.83\_\{\\pm 0\.08\}1\.63×1\.63\\timesQwen3\-8B442\.49±29\.28/208\.59±77\.96442\.49\_\{\\pm 29\.28\}/208\.59\_\{\\pm 77\.96\}1/4\.40±0\.911/4\.40\_\{\\pm 0\.91\}4\.42±0\.29/8\.55±0\.124\.42\_\{\\pm 0\.29\}/8\.55\_\{\\pm 0\.12\}2\.12×2\.12\\timesQwen3\.5\-4B365\.82±24\.10/217\.07±79\.59365\.82\_\{\\pm 24\.10\}/217\.07\_\{\\pm 79\.59\}1/4\.16±0\.921/4\.16\_\{\\pm 0\.92\}3\.66±0\.24/8\.38±0\.203\.66\_\{\\pm 0\.24\}/8\.38\_\{\\pm 0\.20\}1\.69×1\.69\\timesQwen3\.5\-9B491\.59±32\.48/239\.92±79\.83491\.59\_\{\\pm 32\.48\}/239\.92\_\{\\pm 79\.83\}1/4\.73±1\.121/4\.73\_\{\\pm 1\.12\}4\.92±0\.32/10\.57±0\.254\.92\_\{\\pm 0\.32\}/10\.57\_\{\\pm 0\.25\}2\.05×2\.05\\timesGemma4\-12B\-it687\.19±39\.51/411\.00±127\.19687\.19\_\{\\pm 39\.51\}/411\.00\_\{\\pm 127\.19\}1/3\.90±0\.811/3\.90\_\{\\pm 0\.81\}6\.87±0\.40/15\.12±0\.216\.87\_\{\\pm 0\.40\}/15\.12\_\{\\pm 0\.21\}1\.67×1\.67\\timesHumanEvalQwen3\-4B327\.25±20\.07/184\.93±54\.81327\.25\_\{\\pm 20\.07\}/184\.93\_\{\\pm 54\.81\}1/3\.89±1\.041/3\.89\_\{\\pm 1\.04\}3\.27±0\.20/6\.70±0\.113\.27\_\{\\pm 0\.20\}/6\.70\_\{\\pm 0\.11\}1\.77×1\.77\\timesQwen3\-8B447\.42±27\.44/247\.81±73\.78447\.42\_\{\\pm 27\.44\}/247\.81\_\{\\pm 73\.78\}1/3\.72±0\.951/3\.72\_\{\\pm 0\.95\}4\.47±0\.27/8\.59±0\.094\.47\_\{\\pm 0\.27\}/8\.59\_\{\\pm 0\.09\}1\.81×1\.81\\timesQwen3\.5\-4B369\.89±22\.61/231\.97±54\.39369\.89\_\{\\pm 22\.61\}/231\.97\_\{\\pm 54\.39\}1/3\.79±0\.921/3\.79\_\{\\pm 0\.92\}3\.70±0\.23/8\.36±0\.243\.70\_\{\\pm 0\.23\}/8\.36\_\{\\pm 0\.24\}1\.59×1\.59\\timesQwen3\.5\-9B498\.37±30\.48/412\.74±78\.17498\.37\_\{\\pm 30\.48\}/412\.74\_\{\\pm 78\.17\}1/2\.67±0\.461/2\.67\_\{\\pm 0\.46\}4\.98±0\.30/10\.72±0\.214\.98\_\{\\pm 0\.30\}/10\.72\_\{\\pm 0\.21\}1\.21×1\.21\\timesGemma4\-12B\-it687\.16±39\.54/400\.87±82\.35687\.16\_\{\\pm 39\.54\}/400\.87\_\{\\pm 82\.35\}1/3\.93±0\.741/3\.93\_\{\\pm 0\.74\}6\.87±0\.40/15\.19±0\.176\.87\_\{\\pm 0\.40\}/15\.19\_\{\\pm 0\.17\}1\.71×1\.71\\timesMMLUQwen3\-4B327\.51±20\.06/205\.84±62\.37327\.51\_\{\\pm 20\.06\}/205\.84\_\{\\pm 62\.37\}1/3\.59±1\.061/3\.59\_\{\\pm 1\.06\}3\.28±0\.20/6\.82±0\.113\.28\_\{\\pm 0\.20\}/6\.82\_\{\\pm 0\.11\}1\.59×1\.59\\timesQwen3\-8B447\.91±27\.44/298\.07±123\.34447\.91\_\{\\pm 27\.44\}/298\.07\_\{\\pm 123\.34\}1/3\.29±1\.171/3\.29\_\{\\pm 1\.17\}4\.48±0\.27/8\.57±0\.134\.48\_\{\\pm 0\.27\}/8\.57\_\{\\pm 0\.13\}1\.50×1\.50\\timesQwen3\.5\-4B370\.51±22\.60/210\.37±47\.85370\.51\_\{\\pm 22\.60\}/210\.37\_\{\\pm 47\.85\}1/4\.12±0\.811/4\.12\_\{\\pm 0\.81\}3\.71±0\.23/8\.32±0\.173\.71\_\{\\pm 0\.23\}/8\.32\_\{\\pm 0\.17\}1\.76×1\.76\\timesQwen3\.5\-9B493\.44±31\.14/418\.01±122\.83493\.44\_\{\\pm 31\.14\}/418\.01\_\{\\pm 122\.83\}1/2\.72±0\.781/2\.72\_\{\\pm 0\.78\}4\.93±0\.31/10\.52±0\.154\.93\_\{\\pm 0\.31\}/10\.52\_\{\\pm 0\.15\}1\.18×1\.18\\timesGemma4\-12B\-it686\.89±39\.47/452\.21±61\.30686\.89\_\{\\pm 39\.47\}/452\.21\_\{\\pm 61\.30\}1/3\.40±0\.611/3\.40\_\{\\pm 0\.61\}6\.87±0\.39/15\.03±0\.216\.87\_\{\\pm 0\.39\}/15\.03\_\{\\pm 0\.21\}1\.52×1\.52\\timesLCB V6Qwen3\-4B318\.79±19\.56/156\.14±35\.60318\.79\_\{\\pm 19\.56\}/156\.14\_\{\\pm 35\.60\}1/4\.92±0\.761/4\.92\_\{\\pm 0\.76\}3\.19±0\.20/7\.44±0\.143\.19\_\{\\pm 0\.20\}/7\.44\_\{\\pm 0\.14\}2\.04×2\.04\\timesQwen3\-8B432\.26±25\.14/210\.55±51\.09432\.26\_\{\\pm 25\.14\}/210\.55\_\{\\pm 51\.09\}1/4\.85±0\.901/4\.85\_\{\\pm 0\.90\}4\.32±0\.25/9\.77±0\.154\.32\_\{\\pm 0\.25\}/9\.77\_\{\\pm 0\.15\}2\.05×2\.05\\timesQwen3\.5\-4B368\.07±20\.61/182\.61±21\.80368\.07\_\{\\pm 20\.61\}/182\.61\_\{\\pm 21\.80\}1/4\.95±0\.581/4\.95\_\{\\pm 0\.58\}3\.68±0\.21/8\.92±0\.283\.68\_\{\\pm 0\.21\}/8\.92\_\{\\pm 0\.28\}2\.02×2\.02\\timesQwen3\.5\-9B539\.24±30\.92/375\.12±35\.08539\.24\_\{\\pm 30\.92\}/375\.12\_\{\\pm 35\.08\}1/4\.96±0\.471/4\.96\_\{\\pm 0\.47\}5\.39±0\.31/18\.45±0\.515\.39\_\{\\pm 0\.31\}/18\.45\_\{\\pm 0\.51\}1\.44×1\.44\\timesGemma4\-12B\-it685\.34±39\.07/351\.02±53\.96685\.34\_\{\\pm 39\.07\}/351\.02\_\{\\pm 53\.96\}1/4\.47±0\.681/4\.47\_\{\\pm 0\.68\}6\.85±0\.39/15\.35±0\.296\.85\_\{\\pm 0\.39\}/15\.35\_\{\\pm 0\.29\}1\.95×1\.95\\times

Figure 11:PowerMH and PreSTO\-PowerMH on MATH500\.Table 8:EntropyCut execution metrics across base LLMs\.DatasetBase LLMTotal Time \(s\)↓\\downarrowTransitionsper call↑\\uparrowTime/call \(s\)↓\\downarrowSpeedupMATH500\(Fig\.[12](https://arxiv.org/html/2610.13171#A5.F12)\)Qwen3\-4B277\.41±45\.48/157\.85±20\.51277\.41\_\{\\pm 45\.48\}/157\.85\_\{\\pm 20\.51\}1/4\.26±0\.541/4\.26\_\{\\pm 0\.54\}2\.77±0\.45/6\.62±0\.232\.77\_\{\\pm 0\.45\}/6\.62\_\{\\pm 0\.23\}1\.76×1\.76\\timesQwen3\-8B336\.64±58\.87/192\.00±24\.30336\.64\_\{\\pm 58\.87\}/192\.00\_\{\\pm 24\.30\}1/4\.34±0\.471/4\.34\_\{\\pm 0\.47\}3\.37±0\.59/8\.23±0\.273\.37\_\{\\pm 0\.59\}/8\.23\_\{\\pm 0\.27\}1\.75×1\.75\\timesQwen3\.5\-4B365\.78±80\.61/233\.47±73\.77365\.78\_\{\\pm 80\.61\}/233\.47\_\{\\pm 73\.77\}1/3\.81±0\.991/3\.81\_\{\\pm 0\.99\}3\.66±0\.81/8\.22±0\.473\.66\_\{\\pm 0\.81\}/8\.22\_\{\\pm 0\.47\}1\.57×1\.57\\timesQwen3\.5\-9B478\.02±74\.36/272\.29±59\.03478\.02\_\{\\pm 74\.36\}/272\.29\_\{\\pm 59\.03\}1/3\.84±0\.651/3\.84\_\{\\pm 0\.65\}4\.78±0\.74/10\.11±0\.524\.78\_\{\\pm 0\.74\}/10\.11\_\{\\pm 0\.52\}1\.76×1\.76\\timesGemma4\-12B\-it980\.09±240\.16/431\.85±175\.94980\.09\_\{\\pm 240\.16\}/431\.85\_\{\\pm 175\.94\}1/4\.07±2\.001/4\.07\_\{\\pm 2\.00\}9\.80±2\.40/15\.06±1\.379\.80\_\{\\pm 2\.40\}/15\.06\_\{\\pm 1\.37\}2\.27×2\.27\\timesAIME 24&25Qwen3\-4B255\.04±37\.63/150\.54±16\.85255\.04\_\{\\pm 37\.63\}/150\.54\_\{\\pm 16\.85\}1/4\.57±0\.491/4\.57\_\{\\pm 0\.49\}2\.55±0\.38/6\.81±0\.182\.55\_\{\\pm 0\.38\}/6\.81\_\{\\pm 0\.18\}1\.69×1\.69\\timesQwen3\-8B345\.86±62\.77/192\.57±26\.84345\.86\_\{\\pm 62\.77\}/192\.57\_\{\\pm 26\.84\}1/4\.37±0\.561/4\.37\_\{\\pm 0\.56\}3\.46±0\.63/8\.28±0\.303\.46\_\{\\pm 0\.63\}/8\.28\_\{\\pm 0\.30\}1\.80×1\.80\\timesQwen3\.5\-4B405\.21±104\.47/196\.78±41\.26405\.21\_\{\\pm 104\.47\}/196\.78\_\{\\pm 41\.26\}1/4\.29±0\.641/4\.29\_\{\\pm 0\.64\}4\.05±1\.04/8\.20±0\.664\.05\_\{\\pm 1\.04\}/8\.20\_\{\\pm 0\.66\}2\.06×2\.06\\timesQwen3\.5\-9B490\.26±82\.75/277\.80±65\.23490\.26\_\{\\pm 82\.75\}/277\.80\_\{\\pm 65\.23\}1/3\.83±0\.751/3\.83\_\{\\pm 0\.75\}4\.90±0\.83/10\.21±0\.514\.90\_\{\\pm 0\.83\}/10\.21\_\{\\pm 0\.51\}1\.76×1\.76\\timesGemma4\-12B\-it684\.74±165\.29/449\.67±125\.04684\.74\_\{\\pm 165\.29\}/449\.67\_\{\\pm 125\.04\}1/3\.55±0\.851/3\.55\_\{\\pm 0\.85\}6\.85±1\.65/15\.01±0\.696\.85\_\{\\pm 1\.65\}/15\.01\_\{\\pm 0\.69\}1\.52×1\.52\\timesMBPPQwen3\-4B260\.73±60\.29/218\.41±48\.68260\.73\_\{\\pm 60\.29\}/218\.41\_\{\\pm 48\.68\}1/3\.51±1\.251/3\.51\_\{\\pm 1\.25\}2\.61±0\.60/7\.15±0\.202\.61\_\{\\pm 0\.60\}/7\.15\_\{\\pm 0\.20\}1\.19×1\.19\\timesQwen3\-8B367\.12±82\.44/256\.66±96\.78367\.12\_\{\\pm 82\.44\}/256\.66\_\{\\pm 96\.78\}1/4\.00±1\.421/4\.00\_\{\\pm 1\.42\}3\.67±0\.82/9\.02±0\.143\.67\_\{\\pm 0\.82\}/9\.02\_\{\\pm 0\.14\}1\.43×1\.43\\timesQwen3\.5\-4B509\.39±79\.35/207\.31±22\.63509\.39\_\{\\pm 79\.35\}/207\.31\_\{\\pm 22\.63\}1/4\.13±0\.371/4\.13\_\{\\pm 0\.37\}5\.09±0\.79/8\.49±0\.275\.09\_\{\\pm 0\.79\}/8\.49\_\{\\pm 0\.27\}2\.46×2\.46\\timesQwen3\.5\-9B762\.07±70\.82/267\.03±54\.05762\.07\_\{\\pm 70\.82\}/267\.03\_\{\\pm 54\.05\}1/4\.30±0\.921/4\.30\_\{\\pm 0\.92\}7\.62±0\.71/11\.03±0\.177\.62\_\{\\pm 0\.71\}/11\.03\_\{\\pm 0\.17\}2\.85×2\.85\\timesGemma4\-12B\-it1022\.57±156\.01/486\.63±107\.741022\.57\_\{\\pm 156\.01\}/486\.63\_\{\\pm 107\.74\}1/3\.25±0\.731/3\.25\_\{\\pm 0\.73\}10\.23±1\.56/15\.12±1\.0610\.23\_\{\\pm 1\.56\}/15\.12\_\{\\pm 1\.06\}2\.10×2\.10\\timesGPQAQwen3\-4B372\.97±69\.04/178\.64±32\.15372\.97\_\{\\pm 69\.04\}/178\.64\_\{\\pm 32\.15\}1/4\.30±0\.671/4\.30\_\{\\pm 0\.67\}3\.73±0\.69/7\.49±0\.423\.73\_\{\\pm 0\.69\}/7\.49\_\{\\pm 0\.42\}2\.09×2\.09\\timesQwen3\-8B377\.49±64\.81/210\.70±24\.84377\.49\_\{\\pm 64\.81\}/210\.70\_\{\\pm 24\.84\}1/4\.39±0\.501/4\.39\_\{\\pm 0\.50\}3\.77±0\.65/9\.14±0\.383\.77\_\{\\pm 0\.65\}/9\.14\_\{\\pm 0\.38\}1\.79×1\.79\\timesQwen3\.5\-4B397\.44±97\.55/203\.25±52\.71397\.44\_\{\\pm 97\.55\}/203\.25\_\{\\pm 52\.71\}1/4\.36±0\.771/4\.36\_\{\\pm 0\.77\}3\.97±0\.98/8\.50±0\.493\.97\_\{\\pm 0\.98\}/8\.50\_\{\\pm 0\.49\}1\.96×1\.96\\timesQwen3\.5\-9B529\.97±101\.82/269\.92±75\.09529\.97\_\{\\pm 101\.82\}/269\.92\_\{\\pm 75\.09\}1/4\.21±0\.751/4\.21\_\{\\pm 0\.75\}5\.30±1\.02/10\.87±0\.705\.30\_\{\\pm 1\.02\}/10\.87\_\{\\pm 0\.70\}1\.96×1\.96\\timesGemma4\-12B\-it943\.24±225\.03/435\.88±116\.35943\.24\_\{\\pm 225\.03\}/435\.88\_\{\\pm 116\.35\}1/3\.64±0\.721/3\.64\_\{\\pm 0\.72\}9\.43±2\.25/15\.17±1\.479\.43\_\{\\pm 2\.25\}/15\.17\_\{\\pm 1\.47\}2\.16×2\.16\\timesHumanEvalQwen3\-4B380\.83±108\.02/203\.08±60\.14380\.83\_\{\\pm 108\.02\}/203\.08\_\{\\pm 60\.14\}1/3\.68±1\.371/3\.68\_\{\\pm 1\.37\}3\.81±1\.08/6\.83±0\.773\.81\_\{\\pm 1\.08\}/6\.83\_\{\\pm 0\.77\}1\.88×1\.88\\timesQwen3\-8B441\.98±154\.66/215\.14±88\.83441\.98\_\{\\pm 154\.66\}/215\.14\_\{\\pm 88\.83\}1/4\.44±1\.791/4\.44\_\{\\pm 1\.79\}4\.42±1\.55/8\.30±1\.044\.42\_\{\\pm 1\.55\}/8\.30\_\{\\pm 1\.04\}2\.05×2\.05\\timesQwen3\.5\-4B435\.56±105\.27/211\.17±46\.11435\.56\_\{\\pm 105\.27\}/211\.17\_\{\\pm 46\.11\}1/3\.71±0\.761/3\.71\_\{\\pm 0\.76\}4\.36±1\.05/7\.59±1\.064\.36\_\{\\pm 1\.05\}/7\.59\_\{\\pm 1\.06\}2\.06×2\.06\\timesQwen3\.5\-9B767\.76±90\.41/268\.95±108\.36767\.76\_\{\\pm 90\.41\}/268\.95\_\{\\pm 108\.36\}1/4\.78±2\.471/4\.78\_\{\\pm 2\.47\}7\.68±0\.90/10\.56±0\.447\.68\_\{\\pm 0\.90\}/10\.56\_\{\\pm 0\.44\}2\.85×2\.85\\timesGemma4\-12B\-it930\.27±168\.82/401\.23±108\.00930\.27\_\{\\pm 168\.82\}/401\.23\_\{\\pm 108\.00\}1/3\.76±1\.021/3\.76\_\{\\pm 1\.02\}9\.30±1\.69/14\.13±1\.849\.30\_\{\\pm 1\.69\}/14\.13\_\{\\pm 1\.84\}2\.32×2\.32\\timesMMLUQwen3\-4B390\.39±105\.60/192\.26±42\.67390\.39\_\{\\pm 105\.60\}/192\.26\_\{\\pm 42\.67\}1/4\.01±0\.731/4\.01\_\{\\pm 0\.73\}3\.90±1\.06/7\.44±0\.343\.90\_\{\\pm 1\.06\}/7\.44\_\{\\pm 0\.34\}2\.03×2\.03\\timesQwen3\-8B612\.03±184\.09/278\.39±93\.41612\.03\_\{\\pm 184\.09\}/278\.39\_\{\\pm 93\.41\}1/3\.90±1\.151/3\.90\_\{\\pm 1\.15\}6\.12±1\.84/9\.88±0\.426\.12\_\{\\pm 1\.84\}/9\.88\_\{\\pm 0\.42\}2\.20×2\.20\\timesQwen3\.5\-4B395\.79±86\.46/240\.24±86\.12395\.79\_\{\\pm 86\.46\}/240\.24\_\{\\pm 86\.12\}1/3\.75±0\.831/3\.75\_\{\\pm 0\.83\}3\.96±0\.86/8\.39±0\.833\.96\_\{\\pm 0\.86\}/8\.39\_\{\\pm 0\.83\}1\.65×1\.65\\timesQwen3\.5\-9B841\.38±140\.68/352\.80±95\.07841\.38\_\{\\pm 140\.68\}/352\.80\_\{\\pm 95\.07\}1/3\.49±0\.871/3\.49\_\{\\pm 0\.87\}8\.41±1\.41/11\.54±0\.408\.41\_\{\\pm 1\.41\}/11\.54\_\{\\pm 0\.40\}2\.38×2\.38\\timesGemma4\-12B\-it887\.63±220\.26/376\.96±167\.32887\.63\_\{\\pm 220\.26\}/376\.96\_\{\\pm 167\.32\}1/4\.50±2\.021/4\.50\_\{\\pm 2\.02\}8\.88±2\.20/14\.11±1\.678\.88\_\{\\pm 2\.20\}/14\.11\_\{\\pm 1\.67\}2\.35×2\.35\\timesLCB V6Qwen3\-4B250\.62±56\.09/151\.82±26\.30250\.62\_\{\\pm 56\.09\}/151\.82\_\{\\pm 26\.30\}1/4\.19±0\.621/4\.19\_\{\\pm 0\.62\}2\.51±0\.56/6\.20±0\.302\.51\_\{\\pm 0\.56\}/6\.20\_\{\\pm 0\.30\}1\.65×1\.65\\timesQwen3\-8B340\.08±82\.22/220\.38±65\.17340\.08\_\{\\pm 82\.22\}/220\.38\_\{\\pm 65\.17\}1/3\.92±0\.901/3\.92\_\{\\pm 0\.90\}3\.40±0\.82/8\.15±0\.733\.40\_\{\\pm 0\.82\}/8\.15\_\{\\pm 0\.73\}1\.54×1\.54\\timesQwen3\.5\-4B337\.14±37\.91/198\.35±48\.78337\.14\_\{\\pm 37\.91\}/198\.35\_\{\\pm 48\.78\}1/4\.31±0\.591/4\.31\_\{\\pm 0\.59\}3\.37±0\.38/8\.36±1\.403\.37\_\{\\pm 0\.38\}/8\.36\_\{\\pm 1\.40\}1\.70×1\.70\\timesQwen3\.5\-9B463\.80±52\.32/242\.89±35\.93463\.80\_\{\\pm 52\.32\}/242\.89\_\{\\pm 35\.93\}1/4\.22±0\.581/4\.22\_\{\\pm 0\.58\}4\.64±0\.52/10\.08±0\.474\.64\_\{\\pm 0\.52\}/10\.08\_\{\\pm 0\.47\}1\.91×1\.91\\timesGemma4\-12B\-it844\.27±204\.00/472\.94±164\.09844\.27\_\{\\pm 204\.00\}/472\.94\_\{\\pm 164\.09\}1/3\.56±0\.991/3\.56\_\{\\pm 0\.99\}8\.44±2\.04/15\.34±0\.778\.44\_\{\\pm 2\.04\}/15\.34\_\{\\pm 0\.77\}1\.79×1\.79\\times

![Refer to caption](https://arxiv.org/html/2610.13171v1/dataset-math500.all-models.prefetch-budget-20.accept-first-entropycut-mh.png)Figure 12:EntropyCut and PreSTO\-EntropyCut on MATH500\.Table 9:MultiTryMH execution metrics across base LLMs\.DatasetBase LLMTotal Time \(s\)↓\\downarrowTransitionsper call↑\\uparrowTime/call \(s\)↓\\downarrowSpeedupMATH500Qwen3\-4B741\.55±35\.32/322\.90±17\.49741\.55\_\{\\pm 35\.32\}/322\.90\_\{\\pm 17\.49\}1/2\.02±0\.111/2\.02\_\{\\pm 0\.11\}7\.42±0\.35/6\.49±0\.177\.42\_\{\\pm 0\.35\}/6\.49\_\{\\pm 0\.17\}2\.30×2\.30\\timesQwen3\-8B865\.84±42\.90/417\.08±21\.21865\.84\_\{\\pm 42\.90\}/417\.08\_\{\\pm 21\.21\}1/2\.04±0\.101/2\.04\_\{\\pm 0\.10\}8\.66±0\.43/8\.50±0\.188\.66\_\{\\pm 0\.43\}/8\.50\_\{\\pm 0\.18\}2\.08×2\.08\\timesQwen3\.5\-4B2174\.72±142\.35/375\.23±14\.432174\.72\_\{\\pm 142\.35\}/375\.23\_\{\\pm 14\.43\}1/2\.05±0\.081/2\.05\_\{\\pm 0\.08\}21\.75±1\.42/7\.68±0\.1621\.75\_\{\\pm 1\.42\}/7\.68\_\{\\pm 0\.16\}5\.80×5\.80\\timesQwen3\.5\-9B3246\.66±262\.85/463\.26±25\.283246\.66\_\{\\pm 262\.85\}/463\.26\_\{\\pm 25\.28\}1/2\.05±0\.111/2\.05\_\{\\pm 0\.11\}32\.47±2\.63/9\.48±0\.1532\.47\_\{\\pm 2\.63\}/9\.48\_\{\\pm 0\.15\}7\.01×7\.01\\timesGemma4\-12B\-it1558\.70±79\.33/686\.49±45\.491558\.70\_\{\\pm 79\.33\}/686\.49\_\{\\pm 45\.49\}1/1\.86±0\.131/1\.86\_\{\\pm 0\.13\}15\.59±0\.79/12\.75±0\.2015\.59\_\{\\pm 0\.79\}/12\.75\_\{\\pm 0\.20\}2\.27×2\.27\\timesAIME 24&25Qwen3\-4B633\.31±31\.36/313\.16±17\.48633\.31\_\{\\pm 31\.36\}/313\.16\_\{\\pm 17\.48\}1/2\.03±0\.111/2\.03\_\{\\pm 0\.11\}6\.33±0\.31/6\.33±0\.186\.33\_\{\\pm 0\.31\}/6\.33\_\{\\pm 0\.18\}2\.02×2\.02\\timesQwen3\-8B867\.08±41\.03/429\.22±17\.70867\.08\_\{\\pm 41\.03\}/429\.22\_\{\\pm 17\.70\}1/1\.99±0\.061/1\.99\_\{\\pm 0\.06\}8\.67±0\.41/8\.52±0\.208\.67\_\{\\pm 0\.41\}/8\.52\_\{\\pm 0\.20\}2\.02×2\.02\\timesQwen3\.5\-4B2337\.06±148\.90/381\.74±16\.292337\.06\_\{\\pm 148\.90\}/381\.74\_\{\\pm 16\.29\}1/2\.04±0\.091/2\.04\_\{\\pm 0\.09\}23\.37±1\.49/7\.79±0\.1923\.37\_\{\\pm 1\.49\}/7\.79\_\{\\pm 0\.19\}6\.12×6\.12\\timesQwen3\.5\-9B3522\.15±239\.42/510\.54±27\.053522\.15\_\{\\pm 239\.42\}/510\.54\_\{\\pm 27\.05\}1/2\.03±0\.111/2\.03\_\{\\pm 0\.11\}35\.22±2\.39/10\.35±0\.2435\.22\_\{\\pm 2\.39\}/10\.35\_\{\\pm 0\.24\}6\.90×6\.90\\timesGemma4\-12B\-it1705\.50±87\.72/672\.72±34\.821705\.50\_\{\\pm 87\.72\}/672\.72\_\{\\pm 34\.82\}1/2\.05±0\.111/2\.05\_\{\\pm 0\.11\}17\.06±0\.88/13\.79±0\.2817\.06\_\{\\pm 0\.88\}/13\.79\_\{\\pm 0\.28\}2\.54×2\.54\\timesMBPPQwen3\-4B747\.32±38\.12/317\.69±16\.22747\.32\_\{\\pm 38\.12\}/317\.69\_\{\\pm 16\.22\}1/2\.00±0\.101/2\.00\_\{\\pm 0\.10\}7\.47±0\.38/6\.35±0\.167\.47\_\{\\pm 0\.38\}/6\.35\_\{\\pm 0\.16\}2\.35×2\.35\\timesQwen3\-8B857\.30±42\.10/434\.58±29\.62857\.30\_\{\\pm 42\.10\}/434\.58\_\{\\pm 29\.62\}1/1\.96±0\.121/1\.96\_\{\\pm 0\.12\}8\.57±0\.42/8\.50±0\.238\.57\_\{\\pm 0\.42\}/8\.50\_\{\\pm 0\.23\}1\.97×1\.97\\timesQwen3\.5\-4B2083\.62±128\.92/389\.74±22\.832083\.62\_\{\\pm 128\.92\}/389\.74\_\{\\pm 22\.83\}1/1\.97±0\.131/1\.97\_\{\\pm 0\.13\}20\.84±1\.29/7\.66±0\.1520\.84\_\{\\pm 1\.29\}/7\.66\_\{\\pm 0\.15\}5\.35×5\.35\\timesQwen3\.5\-9B3088\.45±181\.21/520\.56±38\.973088\.45\_\{\\pm 181\.21\}/520\.56\_\{\\pm 38\.97\}1/1\.83±0\.131/1\.83\_\{\\pm 0\.13\}30\.88±1\.81/9\.46±0\.1630\.88\_\{\\pm 1\.81\}/9\.46\_\{\\pm 0\.16\}5\.93×5\.93\\timesGemma4\-12B\-it1485\.77±74\.38/682\.29±31\.671485\.77\_\{\\pm 74\.38\}/682\.29\_\{\\pm 31\.67\}1/1\.82±0\.091/1\.82\_\{\\pm 0\.09\}14\.86±0\.74/12\.41±0\.2614\.86\_\{\\pm 0\.74\}/12\.41\_\{\\pm 0\.26\}2\.18×2\.18\\timesGPQAQwen3\-4B760\.17±39\.39/324\.25±18\.52760\.17\_\{\\pm 39\.39\}/324\.25\_\{\\pm 18\.52\}1/1\.97±0\.131/1\.97\_\{\\pm 0\.13\}7\.60±0\.39/6\.38±0\.187\.60\_\{\\pm 0\.39\}/6\.38\_\{\\pm 0\.18\}2\.34×2\.34\\timesQwen3\-8B873\.76±43\.90/427\.11±25\.97873\.76\_\{\\pm 43\.90\}/427\.11\_\{\\pm 25\.97\}1/2\.01±0\.141/2\.01\_\{\\pm 0\.14\}8\.74±0\.44/8\.54±0\.198\.74\_\{\\pm 0\.44\}/8\.54\_\{\\pm 0\.19\}2\.05×2\.05\\timesQwen3\.5\-4B2135\.71±126\.60/378\.95±16\.082135\.71\_\{\\pm 126\.60\}/378\.95\_\{\\pm 16\.08\}1/2\.03±0\.101/2\.03\_\{\\pm 0\.10\}21\.36±1\.27/7\.69±0\.1421\.36\_\{\\pm 1\.27\}/7\.69\_\{\\pm 0\.14\}5\.64×5\.64\\timesQwen3\.5\-9B3197\.39±221\.97/467\.95±19\.993197\.39\_\{\\pm 221\.97\}/467\.95\_\{\\pm 19\.99\}1/2\.04±0\.091/2\.04\_\{\\pm 0\.09\}31\.97±2\.22/9\.51±0\.1731\.97\_\{\\pm 2\.22\}/9\.51\_\{\\pm 0\.17\}6\.83×6\.83\\timesGemma4\-12B\-it1444\.83±69\.75/678\.05±50\.571444\.83\_\{\\pm 69\.75\}/678\.05\_\{\\pm 50\.57\}1/1\.87±0\.151/1\.87\_\{\\pm 0\.15\}14\.45±0\.70/12\.61±0\.2714\.45\_\{\\pm 0\.70\}/12\.61\_\{\\pm 0\.27\}2\.13×2\.13\\timesHumanEvalQwen3\-4B753\.01±39\.06/341\.15±23\.26753\.01\_\{\\pm 39\.06\}/341\.15\_\{\\pm 23\.26\}1/1\.94±0\.141/1\.94\_\{\\pm 0\.14\}7\.53±0\.39/6\.59±0\.187\.53\_\{\\pm 0\.39\}/6\.59\_\{\\pm 0\.18\}2\.21×2\.21\\timesQwen3\-8B867\.99±45\.68/455\.50±29\.38867\.99\_\{\\pm 45\.68\}/455\.50\_\{\\pm 29\.38\}1/1\.89±0\.141/1\.89\_\{\\pm 0\.14\}8\.68±0\.46/8\.56±0\.208\.68\_\{\\pm 0\.46\}/8\.56\_\{\\pm 0\.20\}1\.91×1\.91\\timesQwen3\.5\-4B2179\.86±113\.33/390\.14±23\.082179\.86\_\{\\pm 113\.33\}/390\.14\_\{\\pm 23\.08\}1/1\.97±0\.131/1\.97\_\{\\pm 0\.13\}21\.80±1\.13/7\.66±0\.1921\.80\_\{\\pm 1\.13\}/7\.66\_\{\\pm 0\.19\}5\.59×5\.59\\timesQwen3\.5\-9B3248\.00±177\.40/525\.50±26\.423248\.00\_\{\\pm 177\.40\}/525\.50\_\{\\pm 26\.42\}1/1\.78±0\.091/1\.78\_\{\\pm 0\.09\}32\.48±1\.77/9\.32±0\.1832\.48\_\{\\pm 1\.77\}/9\.32\_\{\\pm 0\.18\}6\.18×6\.18\\timesGemma4\-12B\-it1473\.37±73\.60/680\.25±59\.151473\.37\_\{\\pm 73\.60\}/680\.25\_\{\\pm 59\.15\}1/1\.89±0\.111/1\.89\_\{\\pm 0\.11\}14\.73±0\.74/12\.81±1\.1714\.73\_\{\\pm 0\.74\}/12\.81\_\{\\pm 1\.17\}2\.17×2\.17\\timesMMLUQwen3\-4B736\.92±35\.99/345\.12±28\.39736\.92\_\{\\pm 35\.99\}/345\.12\_\{\\pm 28\.39\}1/1\.85±0\.171/1\.85\_\{\\pm 0\.17\}7\.37±0\.36/6\.35±0\.227\.37\_\{\\pm 0\.36\}/6\.35\_\{\\pm 0\.22\}2\.14×2\.14\\timesQwen3\-8B858\.38±44\.28/446\.25±28\.97858\.38\_\{\\pm 44\.28\}/446\.25\_\{\\pm 28\.97\}1/1\.90±0\.151/1\.90\_\{\\pm 0\.15\}8\.58±0\.44/8\.44±0\.198\.58\_\{\\pm 0\.44\}/8\.44\_\{\\pm 0\.19\}1\.92×1\.92\\timesQwen3\.5\-4B2445\.00±125\.15/384\.31±22\.862445\.00\_\{\\pm 125\.15\}/384\.31\_\{\\pm 22\.86\}1/2\.01±0\.121/2\.01\_\{\\pm 0\.12\}24\.45±1\.25/7\.70±0\.1524\.45\_\{\\pm 1\.25\}/7\.70\_\{\\pm 0\.15\}6\.36×6\.36\\timesQwen3\.5\-9B3764\.61±197\.19/544\.38±54\.163764\.61\_\{\\pm 197\.19\}/544\.38\_\{\\pm 54\.16\}1/1\.82±0\.211/1\.82\_\{\\pm 0\.21\}37\.65±1\.97/9\.81±0\.2137\.65\_\{\\pm 1\.97\}/9\.81\_\{\\pm 0\.21\}6\.92×6\.92\\timesGemma4\-12B\-it1673\.76±80\.51/717\.93±43\.531673\.76\_\{\\pm 80\.51\}/717\.93\_\{\\pm 43\.53\}1/1\.92±0\.121/1\.92\_\{\\pm 0\.12\}16\.74±0\.81/13\.74±0\.2116\.74\_\{\\pm 0\.81\}/13\.74\_\{\\pm 0\.21\}2\.33×2\.33\\timesLCB V6Qwen3\-4B781\.77±48\.77/337\.69±8\.76781\.77\_\{\\pm 48\.77\}/337\.69\_\{\\pm 8\.76\}1/1\.96±0\.061/1\.96\_\{\\pm 0\.06\}7\.82±0\.49/6\.61±0\.167\.82\_\{\\pm 0\.49\}/6\.61\_\{\\pm 0\.16\}2\.32×2\.32\\timesQwen3\-8B908\.99±62\.75/436\.38±22\.48908\.99\_\{\\pm 62\.75\}/436\.38\_\{\\pm 22\.48\}1/2\.00±0\.131/2\.00\_\{\\pm 0\.13\}9\.09±0\.63/8\.69±0\.259\.09\_\{\\pm 0\.63\}/8\.69\_\{\\pm 0\.25\}2\.08×2\.08\\timesQwen3\.5\-4B2197\.08±189\.19/381\.58±12\.132197\.08\_\{\\pm 189\.19\}/381\.58\_\{\\pm 12\.13\}1/2\.04±0\.091/2\.04\_\{\\pm 0\.09\}21\.97±1\.89/7\.79±0\.2221\.97\_\{\\pm 1\.89\}/7\.79\_\{\\pm 0\.22\}5\.76×5\.76\\timesQwen3\.5\-9B3260\.87±315\.74/474\.97±21\.883260\.87\_\{\\pm 315\.74\}/474\.97\_\{\\pm 21\.88\}1/2\.03±0\.091/2\.03\_\{\\pm 0\.09\}32\.61±3\.16/9\.62±0\.2232\.61\_\{\\pm 3\.16\}/9\.62\_\{\\pm 0\.22\}6\.87×6\.87\\timesGemma4\-12B\-it1494\.62±85\.17/673\.93±96\.531494\.62\_\{\\pm 85\.17\}/673\.93\_\{\\pm 96\.53\}1/1\.93±0\.191/1\.93\_\{\\pm 0\.19\}14\.95±0\.85/12\.88±0\.8714\.95\_\{\\pm 0\.85\}/12\.88\_\{\\pm 0\.87\}2\.22×2\.22\\times

### E\.2Case Study 2: Effect of prefetch budget

Setting\.On LCB V6 with Qwen3\.5\-9B under the default BFS traversal atK=100K=100, we compare PreSTO\-PowerMH atNpf∈\{8,10,12,16,20\}N\_\{\\mathrm\{pf\}\}\\in\\\{8,10,12,16,20\\\}with PowerMH\. The PreSTO\-PowerMH runs are the BFS runs of Case Study 5 and the PowerMH run is the vLLM run of Case Study 6; all share one host and were recorded within three days \(Appendix\)\. These runs did not record KV\-pool use or prefix\-cache statistics, and no LCB V6 sweep of PreSTO\-EntropyCut is available\.

Results\.Figure[13](https://arxiv.org/html/2610.13171#A5.F13)shows the traces of every budget over theK=100K=100realized MH transitions, and confirms the findings of Section[5\.2](https://arxiv.org/html/2610.13171#S5.SS2)\.

- •Transitions per call grow with the budget\.They rise from3\.593\.59atNpf=8N\_\{\\mathrm\{pf\}\}=8to4\.914\.91at the defaultNpf=20N\_\{\\mathrm\{pf\}\}=20\(Table[2](https://arxiv.org/html/2610.13171#S5.T2)\)\.
- •Each call slows with the budget, so the speedup grows more slowly\.A PreSTO\-PowerMH call takes16\.216\.2–18\.418\.4seconds, versus5\.45\.4seconds for a PowerMH step, so the speedup over PowerMH rises from1\.20×1\.20\\timesatNpf=8N\_\{\\mathrm\{pf\}\}=8to1\.44×1\.44\\timesatNpf=20N\_\{\\mathrm\{pf\}\}=20, the largest budget tested\.

Figure 13:Per\-transition traces across prefetch budgets on LCB V6 with Qwen3\.5\-9B\.Solid curves show the PreSTO mean for each budget, from light \(smallNpfN\_\{\\mathrm\{pf\}\}\) to dark \(largeNpfN\_\{\\mathrm\{pf\}\}\)\. Dashed curves show PowerMH, and shaded bands show±1\\pm 1SD over traces\.
### E\.3Case Study 3: Likelihood and confidence

Setting\.Following[Karan and Du \(2026\)](https://arxiv.org/html/2610.13171#bib.bib28), we describe each terminal trace by its token\-normalized log\-likelihood \(Eq\.[21](https://arxiv.org/html/2610.13171#A4.E21)\) and confidence \(Eq\.[22](https://arxiv.org/html/2610.13171#A4.E22)\) underp0p\_\{0\}\. We compare each sampler with its PreSTO variant atNpf=20N\_\{\\mathrm\{pf\}\}=20on matched dataset–base\-LLM pairs: PowerMH against PreSTO\-PowerMH, and EntropyCut against PreSTO\-EntropyCut\.

For each pair and statistic, we apply the paired TOST of Appendix[D](https://arxiv.org/html/2610.13171#A4)to the per\-prompt difference, PreSTO minus baseline, with marginδ=0\.2\\delta=0\.2baseline standard deviations across prompts\. For each sampler, we also pool the standardized differences \(each difference divided by that standard deviation\) over its pairs with a fixed\-effect average and test the pooled difference against the same margin\.

We compare both statistics only within each base LLM, because changingp0p\_\{0\}changes the scoring distribution itself\.

Figure 14:Likelihood and confidence distributions with and without PreSTO\.Boxes show the per\-prompt token\-normalized log\-likelihood \(a, c\) and confidence \(b, d\) of terminal traces underp0p\_\{0\}for the eight PowerMH pairs \(top\) and the eleven EntropyCut pairs \(bottom\), each against its PreSTO variant\. Shaded rows are equivalent under the paired TOST \(peq<0\.05p\_\{\\mathrm\{eq\}\}<0\.05\)\.Results\.Figure[14](https://arxiv.org/html/2610.13171#A5.F14)shows all retained pairs and confirms the findings of Section[5\.2](https://arxiv.org/html/2610.13171#S5.SS2)\.

- •Equivalence holds for most tests\.29 of the 38 tests establish equivalence: 12 of 16 for PowerMH and 17 of 22 for EntropyCut \(shaded rows\)\. For PowerMH with Qwen3\.5\-4B, these include 7 of the 10 tests of Figure[6](https://arxiv.org/html/2610.13171#S5.F6)\.
- •Means nearly coincide\.The median absolute gap between the PreSTO and baseline means is0\.0020\.002in log\-likelihood for both samplers, and0\.0070\.007for PowerMH and0\.0040\.004for EntropyCut in confidence, against across\-prompt standard deviations of about0\.050\.05and0\.100\.10\.

### E\.4Case Study 4: Distribution ofϵ\\epsilon\-certainty

Setting\.This case study extends the certainty analysis of Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3)to more base LLMs, more datasets, and the EntropyCut proposal rule\. Withϵ=0\.01\\epsilon=0\.01, an MH decision with acceptance probabilityAAis anϵ\\epsilon\-certain reject ifA≤ϵA\\leq\\epsilon, anϵ\\epsilon\-certain accept ifA≥1−ϵA\\geq 1\-\\epsilon, andϵ\\epsilon\-uncertain otherwise\.

The histograms count both outgoing edges of every scored decision, with transition probabilitiesAAand1−A1\-A, and call an edgeϵ\\epsilon\-certain when its transition probability is at mostϵ\\epsilonor at least1−ϵ1\-\\epsilon; the two outer categories therefore have equal mass, and their combined share equals the fraction ofϵ\\epsilon\-certain decisions\.

Figure 15:Edge certainty under PreSTO\-PowerMH across models and datasets\.Figure 16:Edge certainty under PreSTO\-EntropyCut across models and datasets\.Results\.Figures[15](https://arxiv.org/html/2610.13171#A5.F15)and[16](https://arxiv.org/html/2610.13171#A5.F16)confirm the findings of Section[5\.2](https://arxiv.org/html/2610.13171#S5.SS2)\. We find that Most decisions areϵ\\epsilon\-certain\. Under PreSTO\-PowerMH,56%56\\%–95%95\\%of edges areϵ\\epsilon\-certain for the Qwen models and67%67\\%–78%78\\%for Gemma4\-12B\-it; under PreSTO\-EntropyCut,60%60\\%–92%92\\%and60%60\\%–93%93\\%\.

### E\.5Case Study 5: Effect of traversal rules

We compare the predictive traversal rule \(Appendix[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)\) with the default BFS traversal; Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)evaluates the classifier that supplies its class probabilities\.

Setting\.We run PreSTO\-PowerMH with the default BFS traversal and with the predictive traversal rule on LCB V6 with Qwen3\.5\-9B, usingNpf∈\{8,10,12,16,20\}N\_\{\\mathrm\{pf\}\}\\in\\\{8,10,12,16,20\\\}\. The classifier of the predictive rule is the cut\-fraction logistic regression of Appendix[E\.7](https://arxiv.org/html/2610.13171#A5.SS7)\.

Table 10:Predictive traversal rule against the default BFS traversal\.Speedup is the total model\-call time of BFS divided by that of the predictive rule\.Model callsTransitions per callTime per call \(s\)Model\-call time \(s\)NpfN\_\{\\mathrm\{pf\}\}BFSPredictiveBFSPredictiveBFSPredictiveBFSPredictiveSpeedup827\.8523\.403\.594\.2716\.1515\.35449\.7±19\.1449\.7\_\{\\pm 19\.1\}359\.2±28\.0\\mathbf\{359\.2\}\_\{\\pm 28\.0\}1\.25×1\.25\\times1025\.4020\.153\.944\.9616\.5616\.00420\.7±25\.5420\.7\_\{\\pm 25\.5\}322\.3±28\.5\\mathbf\{322\.3\}\_\{\\pm 28\.5\}1\.31×1\.31\\times1223\.4018\.904\.275\.2917\.5817\.13411\.4±38\.7411\.4\_\{\\pm 38\.7\}323\.8±39\.5\\mathbf\{323\.8\}\_\{\\pm 39\.5\}1\.27×1\.27\\times1621\.6017\.104\.635\.8518\.1517\.34392\.1±33\.8392\.1\_\{\\pm 33\.8\}296\.6±45\.8\\mathbf\{296\.6\}\_\{\\pm 45\.8\}1\.32×1\.32\\times2020\.3515\.304\.916\.5418\.4317\.95375\.1±35\.1375\.1\_\{\\pm 35\.1\}274\.7±40\.1\\mathbf\{274\.7\}\_\{\\pm 40\.1\}1\.37×1\.37\\times

Results\.

- •Faster at every budget\.The predictive rule is1\.25×1\.25\\times–1\.37×1\.37\\timesfaster than BFS in model\-call time \(Figure[7](https://arxiv.org/html/2610.13171#S5.F7)and Table[10](https://arxiv.org/html/2610.13171#A5.T10)\) and faster on 98 of the 100 prompt–budget pairs\.
- •The gain comes from fewer model calls\.The predictive rule completes19%19\\%–33%33\\%more MH transitions per call, so it needs1\.19×1\.19\\times–1\.33×1\.33\\timesfewer calls for the sameKK\(Figure[7](https://arxiv.org/html/2610.13171#S5.F7)\(a\)\); its time per call is also2\.6%2\.6\\%–4\.9%4\.9\\%shorter \(Figure[7](https://arxiv.org/html/2610.13171#S5.F7)\(b\)\)\.
- •The gain is largest atNpf=20N\_\{\\mathrm\{pf\}\}=20\(1\.37×1\.37\\times\), where the predictive rule raises the transitions per call from4\.914\.91to6\.546\.54\.

Figures[7](https://arxiv.org/html/2610.13171#S5.F7)\(d\) and[17](https://arxiv.org/html/2610.13171#A5.F17)show the first prefetched subtree of prompt 0 and of prompts 1–3 under each rule at every budget, one prompt and rule per row\. The predictive rule realizes more transitions in 11 of the 20 prompt–budget pairs and fewer in 8 \(59 against 52 in total\), so its speedup in Table[10](https://arxiv.org/html/2610.13171#A5.T10)reflects an average over all trees rather than a gain on every tree\.

Npf=8N\_\{\\mathrm\{pf\}\}=8Npf=10N\_\{\\mathrm\{pf\}\}=10Npf=12N\_\{\\mathrm\{pf\}\}=12Npf=16N\_\{\\mathrm\{pf\}\}=16Npf=20N\_\{\\mathrm\{pf\}\}=20

Figure 17:First prefetched subtree under each traversal rule and prefetch budget\.Prompts 1–3 of LCB V6 with Qwen3\.5\-9B under PreSTO\-PowerMH, one row per prompt and rule; labels and colors follow Figure[7](https://arxiv.org/html/2610.13171#S5.F7)d\.
### E\.6Case Study 6: Effect of different serving engines

Setting\.All main results use vLLM; to check that the acceleration is not specific to it, we also run PowerMH and PreSTO\-PowerMH on SGLang\. The two engines draw different random samples, so their chains and numbers of calls differ\.

Table 11:PowerMH and PreSTO\-PowerMH on vLLM and SGLang\.EngineSamplerCallsTime per call \(s\)Model\-call time \(s\)SpeedupvLLMPowerMH1001005\.39±0\.315\.39\_\{\\pm 0\.31\}539\.24±30\.92539\.24\_\{\\pm 30\.92\}1\.40×1\.40\\timesPreSTO\-PowerMH20\.60±1\.3120\.60\_\{\\pm 1\.31\}18\.75±0\.4318\.75\_\{\\pm 0\.43\}385\.97±21\.25385\.97\_\{\\pm 21\.25\}SGLangPowerMH1001003\.57±0\.243\.57\_\{\\pm 0\.24\}357\.40±23\.67357\.40\_\{\\pm 23\.67\}1\.97×1\.97\\timesPreSTO\-PowerMH21\.25±1\.8621\.25\_\{\\pm 1\.86\}8\.56±0\.108\.56\_\{\\pm 0\.10\}181\.74±15\.25181\.74\_\{\\pm 15\.25\}Results\.PreSTO\-PowerMH is faster than PowerMH under both engines, so the acceleration is not specific to vLLM \(Table[11](https://arxiv.org/html/2610.13171#A5.T11)\)\.

- •The speedup is larger under SGLang\(1\.97×1\.97\\timesagainst1\.40×1\.40\\timesunder vLLM\)\. Both engines cut the number of calls by a similar factor \(4\.7×4\.7\\timesand4\.9×4\.9\\times\), but a PreSTO\-PowerMH call costs2\.4×2\.4\\timesa PowerMH step under SGLang against3\.5×3\.5\\timesunder vLLM\.
- •SGLang is faster in absolute time:1\.5×1\.5\\timesfaster than vLLM for PowerMH and2\.1×2\.1\\timesfor PreSTO\-PowerMH\.

### E\.7Case Study 7: Predictingϵ\\epsilon\-certainty before generation

The predictive traversal rule \(Appendix[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)\) needs the class probabilitiesP^​\(v​isϵ\-certain reject\)\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain reject\}\)andP^​\(v​isϵ\-certain accept\)\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain accept\}\)of every candidate nodevvbefore the proposal atv\+v^\{\+\}is generated\. We therefore predict, from information available before generation, which of the three classes of Section[3\.3](https://arxiv.org/html/2610.13171#S3.SS3)each candidate node falls into: certain reject \(A≤ϵA\\leq\\epsilon\), certain accept \(A≥1−ϵA\\geq 1\-\\epsilon\), or uncertain \(ϵ<A<1−ϵ\\epsilon<A<1\-\\epsilon\)\. We use the results to choose the input features and the model of the rule\.

Setting\.Each run records the acceptance probabilityA=A⁡\(v\+,v\)A=A\(v^\{\+\},v\)of every prefetched node, and these nodes are the examples\. We use one run per sampler, on the first 20 prompts of LCB V6 with Qwen3\.5\-9B\. The PreSTO\-PowerMH dataset has4,6214\{,\}621nodes from579579model calls:2,8142\{,\}814ϵ\\epsilon\-certain rejects,945945ϵ\\epsilon\-certain accepts, and862862ϵ\\epsilon\-uncertain\. The PreSTO\-EntropyCut dataset has4,5334\{,\}533nodes from568568model calls:2,7012\{,\}701,880880, and952952, respectively\. These are about88nodes per call, fewer thanNpf=10N\_\{\\mathrm\{pf\}\}=10, for two reasons\. First, the calls issue5,6905\{,\}690and5,5465\{,\}546requests; we drop the1,0691\{,\}069and1,0131\{,\}013requests that BFS places below the rejection child of a node whose acceptance\-child request it deferred under Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), because the MH walk of that call stops at that node and does not reach them\. Second,2121and2222calls near the end of a prompt, when at most66of theKKtransitions remain, issue fewer than1010requests\. Because the examples are the nodes that BFS actually prefetched, they follow the distribution of the prefetched subtree, not that of all candidate nodes\. We group the features, all available when the batch is assembled, into four sets:

- •Feature 1 \(cut fraction\):the cut fractioncj/Tc\_\{j\}/Tof the request, wherevjv\_\{j\}is the acceptance child of the nodeviv\_\{i\}\(that is,vi=vv\_\{i\}=vandvj=v\+v\_\{j\}=v^\{\+\}\)\.
- •Feature 2 \(tree position\):the cut indexcic\_\{i\}ofviv\_\{i\}, the gapci−cjc\_\{i\}\-c\_\{j\}, the depth ofviv\_\{i\}, and the number of acceptances on the path from the root toviv\_\{i\}\.
- •Feature 3 \(likelihood\):four statistics of the token\-wise log\-likelihood of the root state under the proposal LLM: its value at the first resampled token, its changes into and out of that token, and its mean over the suffix after the cut\.
- •Feature 4 \(entropy, PreSTO\-EntropyCut only\):the same four statistics of the token\-wise entropy of the root state; the uniform\-cut run did not log token entropies\.

Classifier\.Each nodevvhas a standardized feature vectorx∈ℝdx\\in\\mathbb\{R\}^\{d\}and a true classy⁡\(v\)∈\{1,2,3\}y\(v\)\\in\\\{1,2,3\\\}:ϵ\\epsilon\-certain reject,ϵ\\epsilon\-certain accept, orϵ\\epsilon\-uncertain, in the order of Appendix[C\.3](https://arxiv.org/html/2610.13171#A3.SS3)\. We use a three\-class logistic regression, that is, a linear layer with weightsWWfollowed by a softmax over the three classes\. It thus outputsP^​\(v​isϵ\-certain reject\)\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain reject\}\)andP^​\(v​isϵ\-certain accept\)\\widehat\{P\}\(v\\text\{ is $\\epsilon$\-certain accept\}\)directly, and their sum is at most one by construction\. To test whether a nonlinear model helps, we also train multilayer perceptrons that insert hidden layers with theReLU\\operatorname\{ReLU\}activation before the softmax; with one hidden layer,

P^\(y=k∣v\)=softmaxk\(W2ReLU\(W1x\+b1\)\+b2\),k=1,2,3,\\widehat\{P\}\(y=k\\mid v\)=\\operatorname\{softmax\}\_\{k\}\\bigl\(W\_\{2\}\\operatorname\{ReLU\}\(W\_\{1\}x\+b\_\{1\}\)\+b\_\{2\}\\bigr\),\\qquad k=1,2,3,\(24\)and a second hidden layer adds another linear layer followed byReLU\\operatorname\{ReLU\}; we use one hidden layer of1616,3232, or6464units, or two hidden layers of3232or6464units each\. All models are trained to minimize the log loss \(cross\-entropy\) on a training dataset𝒟\\mathcal\{D\}of nodes,

ℒ\(𝒟\)=−1\|𝒟\|∑v∈𝒟logP^\(y=y\(v\)∣v\),\\mathcal\{L\}\(\\mathcal\{D\}\)=\-\\frac\{1\}\{\|\\mathcal\{D\}\|\}\\sum\_\{v\\in\\mathcal\{D\}\}\\log\\widehat\{P\}\\bigl\(y=y\(v\)\\mid v\\bigr\),\(25\)with the natural logarithm, plus theL2L\_\{2\}penaltyλ2​\|𝒟\|\\frac\{\\lambda\}\{2\|\\mathcal\{D\}\|\}times the sum of squared weights, biases excluded:λ=1\\lambda=1for the logistic regression \(scikit\-learn’sC=1/λ=1\\,=1/\\lambda=1\), andλ=10−3\\lambda=10^\{\-3\}for the multilayer perceptrons \(scikit\-learn’salpha\), which are trained with Adam and stopped early on a10%10\\%validation split of the training fold\.

Evaluation metrics\.We evaluate each classifier by 5\-fold cross\-validation with whole prompts held out and pool the out\-of\-fold predictions, so every nodevvin the set𝒰\\mathcal\{U\}of all nodes is scored by a model that never saw its prompt\. Letsk​\(v\)=P^​\(y=k∣v\)s\_\{k\}\(v\)=\\widehat\{P\}\(y=k\\mid v\)be the held\-out probability of classkk\. We report two metrics, each against a constant baseline that ignores the features:

- •Accuracy:the fraction of nodes whose most likely classy^​\(v\)=arg⁡maxk​sk​\(v\)\\hat\{y\}\(v\)=\\arg\\max\_\{k\}s\_\{k\}\(v\)equalsy⁡\(v\)y\(v\); the baseline always predicts the most frequent class\.
- •Log loss:ℒ⁡\(𝒰\)\\mathcal\{L\}\(\\mathcal\{U\}\)in \([25](https://arxiv.org/html/2610.13171#A5.E25)\), computed with the held\-out probabilitiessk​\(v\)s\_\{k\}\(v\); the baseline predicts the class frequencies for every node\.

Log loss scores the predicted probabilities, which the predictive traversal rule uses; accuracy scores only the most likely classy^​\(v\)\\hat\{y\}\(v\)\.

Figure 18:Prediction of theϵ\\epsilon\-certainty class by feature set\.Held\-out accuracy against log loss of the logistic regression for PreSTO\-PowerMH \(a\) and PreSTO\-EntropyCut \(b\); upper left is better\. Labels give the feature sets used: a single digit is one set, “1\+3” combines Features 1 and 3, and “1–3” combines Features 1 through 3; comma\-separated labels mark overlapping points\. The cross marks the constant baseline, and the bold label is the configuration we use\.Figure 19:Effect of hidden layers on predicting theϵ\\epsilon\-certainty class\.Held\-out accuracy against log loss with the cut fraction as the only feature; labels give the units per hidden layer, and “none” is the logistic regression\. Markers as in Figure[18](https://arxiv.org/html/2610.13171#A5.F18)\.Results\.We use the logistic regression with the cut fractioncj/Tc\_\{j\}/Tas the only feature\. It reaches a held\-out accuracy of0\.6430\.643under PreSTO\-PowerMH and0\.6250\.625under PreSTO\-EntropyCut, above the majority\-class rates of0\.6090\.609and0\.5960\.596, and lowers the log loss from0\.9400\.940to0\.8190\.819and from0\.9540\.954to0\.8840\.884relative to the class prior \(Figure[18](https://arxiv.org/html/2610.13171#A5.F18)\)\. The other choices are not useful\.

### E\.8Case Study 8: Comparison with test\-time baselines

PreSTO\-PowerMH speeds up PowerMH without changing its transition kernel, but PowerMH is only one way to spend test\-time compute\. This case study places both among three baselines that also sharpen the base distribution or select among samples: low\-temperature sampling, best\-of\-NN\([Stiennon et al\., 2020](https://arxiv.org/html/2610.13171#bib.bib52);[Sun et al\., 2024](https://arxiv.org/html/2610.13171#bib.bib54)\), and PowerSMC\([Azizi et al\., 2026](https://arxiv.org/html/2610.13171#bib.bib5)\)\. Low\-temperature sampling and best\-of\-NNdo not targetp0αp\_\{0\}^\{\\alpha\}: scaling each token’s logits byα\\alpharenormalizes every conditional separately, which differs from the sequence\-level power distribution\([Karan and Du, 2026](https://arxiv.org/html/2610.13171#bib.bib28)\)\. We compare their generation time, peak KV\-pool use, and accuracy on the same prompts\.

Setting\.All runs use the first2020prompts of LCB V6 with Qwen3\.5\-9B, process one prompt at a time on vLLM, and targetα=4\\alpha=4\. PowerMH and PreSTO\-PowerMH ignore the end\-of\-sequence token and always generate all1,0241\{,\}024new tokens, whereas low\-temperature sampling, best\-of\-NN, and PowerSMC stop a sample at the end\-of\-sequence token, so they generate up to1,0241\{,\}024new tokens\. PowerMH and PreSTO\-PowerMH run a single block ofK∈\{10,20,30\}K\\in\\\{10,20,30\\\}MH transitions, fewer than theK=100K=100of the main runs, and PreSTO\-PowerMH uses the default BFS traversal atNpf=10N\_\{\\mathrm\{pf\}\}=10\. Low\-temperature sampling draws one sample at temperature1/α=0\.251/\\alpha=0\.25; best\-of\-NNdrawsN∈\{4,8,16,32\}N\\in\\\{4,8,16,32\\\}samples at the same temperature and keeps the one with the highest unnormalized sequence log\-probability, the sum of its token log\-probabilities under this temperature\-0\.250\.25sampling distribution rather than underp0p\_\{0\}\. PowerSMC growsP∈\{2,4,8,16,32\}P\\in\\\{2,4,8,16,32\\\}particles in blocks of128128tokens, resamples when the effective sample size falls below half, and ramps the exponent toα\\alphaover the first400400tokens\. Time is the generation time per prompt, excluding model loading and grading, and peak KV\-pool use is the largest fraction of the preallocated KV pool in use\. Figure[20](https://arxiv.org/html/2610.13171#A5.F20)plots peak KV\-pool use against time\.

Figure 20:Speed and memory against test\-time baselines\.Peak KV\-pool use against time per prompt on the first 20 prompts of LCB V6 with Qwen3\.5\-9B; lower left is better\.Results\.Figure[20](https://arxiv.org/html/2610.13171#A5.F20)shows that prefetching raises peak KV\-pool use, but by less than the parallel baselines at their larger settings\. Best\-of\-NNand PowerSMC decode all samples or particles at once, so their peak KV\-pool use grows withNNorPP, reaching12\.7%12\.7\\%of the pool atN=32N=32and8\.5%8\.5\\%atP=32P=32\. PreSTO\-PowerMH batches1010proposals and peaks at2\.9%2\.9\\%–3\.1%3\.1\\%at everyKK, close to best\-of\-88\(3\.3%3\.3\\%\), compared with0\.6%0\.6\\%for PowerMH\. PreSTO\-PowerMH therefore narrows, but does not close, the cost gap between PowerMH and these baselines\.

### E\.9Example prefetched\-subtree trajectory

We print the raw log of one prefetched subtree\. Each line of the log is a nodeviv\_\{i\}, printed asNode\(id=ii, cut\_idx=cic\_\{i\}\)\. Nodeviv\_\{i\}has acceptance childv2​i\+1v\_\{2i\+1\}and rejection childv2​i\+2v\_\{2i\+2\}; the rejection child keeps its parent’s state and cut index\. Each acceptance edge carrieslog\_mh\_ratio, the unclamped log MH ratio of the proposal atv2​i\+1v\_\{2i\+1\}, so the edge is taken with probabilitymin⁡\{1,exp⁡\(log\_mh\_ratio\)\}\\min\\\{1,\\exp\(\\texttt\{log\\\_mh\\\_ratio\}\)\\\}; rejection edges carry no value\. The tree holds 16 of the 20 requests in the batch\. The other 4 lie below the rejection child of a node whose own request violates Condition[1](https://arxiv.org/html/2610.13171#Thmcondition1), such asv9v\_\{9\}; the chain cannot pass such a node in this batch, so the sampler does not attach these requests, and the budget runs out before BFS reaches frontier nodes such asv30v\_\{30\}\.

Box 1: Prefetched tree

Box 2: MH progress 0/100→\\rightarrow2/100 \(2 transitions\)[⬇](data:text/plain;base64,c2FtcGxlZCBwYXRoIGluIHRoZSBwcmVmZXRjaGVkIHN1YnRyZWU6IDAg4oaSIDEg4oaSIDMK)sampledpathintheprefetchedsubtree:0→\\rightarrow1→\\rightarrow3

The sampled path \(Box[E\.9](https://arxiv.org/html/2610.13171#A5.SS9)\) accepts atv0v\_\{0\}andv1v\_\{1\}, advancing the chain from step 0 to step 2\. Both decisions areϵ\\epsilon\-certain atϵ=0\.01\\epsilon=0\.01: the ratio atv0v\_\{0\}accepts with probability above0\.99990\.9999, andv1v\_\{1\}accepts with probability 1\. Theϵ\\epsilon\-rounded tree \(Box[E\.9](https://arxiv.org/html/2610.13171#A5.SS9); Definition[1](https://arxiv.org/html/2610.13171#Thmdefinition1)\) drops each branch that rounding assigns zero probability, together with its descendants, and keeps both branches at uncertain decisions, so here it reduces to the single pathv0→v1→v3v\_\{0\}\\to v\_\{1\}\\to v\_\{3\}, which is the sampled path\.

Box 3:ϵ\\epsilon\-rounded tree \(ϵ=0\.01\\epsilon=0\.01\)

#### Binary\-tree views of prefetched subtrees\.

We plot all 19 prefetched subtrees for prompt index 0 from the Qwen3\.5\-9B run on LCB V6 with prefetch budgetNpf=20N\_\{\\mathrm\{pf\}\}=20\. Figure[E\.9](https://arxiv.org/html/2610.13171#A5.SS9.SSS0.Px1)shows them in sampling order; together they cover the chain’s full trajectory of 100 MH transitions\.

\(1\) MH0→20\\rightarrow 2

\(2\) MH2→72\\rightarrow 7

\(3\) MH7→107\\rightarrow 10

\(4\) MH10→1510\\rightarrow 15

\(5\) MH15→2115\\rightarrow 21

\(6\) MH21→2821\\rightarrow 28

\(7\) MH28→3528\\rightarrow 35

\(8\) MH35→4335\\rightarrow 43

\(9\) MH43→4943\\rightarrow 49

\(10\) MH49→5649\\rightarrow 56

\(11\) MH56→6056\\rightarrow 60

\(12\) MH60→6260\\rightarrow 62

\(13\) MH62→6962\\rightarrow 69

\(14\) MH69→7569\\rightarrow 75

\(15\) MH75→8175\\rightarrow 81

\(16\) MH81→8681\\rightarrow 86

\(17\) MH86→9386\\rightarrow 93

\(18\) MH93→9993\\rightarrow 99

\(19\) MH99→10099\\rightarrow 100

\\@makecaption

Figure 21Prefetched subtrees along one full MH trajectory\.The 19 subtrees of prompt 0 \(0\-based\) in sampling order, covering its 100 MH transitions \(LCB V6, Qwen3\.5\-9B, PreSTO\-PowerMH, BFS,Npf=20N\_\{\\mathrm\{pf\}\}=20\)\. Each label gives the MH steps the subtree advances\. Solid left edges: acceptance; dashed right edges: rejection; orange:ϵ\\epsilon\-rounded subtree \(ϵ=0\.01\\epsilon=0\.01, Definition[1](https://arxiv.org/html/2610.13171#Thmdefinition1)\); blue: sampled path \(endpoint double\-bordered\); gray: other prefetched branches\.