acceptodds
Under review as a conference paper at ICLR 2027

PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling

10 views

Abstract

Power sampling improves large language model (LLM) reasoning at test time by sampling from a sharpened distribution over the base model. Its sampler, PowerMH, is slow because its Metropolis–Hastings (MH) updates are sequential: each accept/reject decision sets the state for the next proposal. Prior work cuts this cost by changing the sampler or the model (e.g., sequential Monte Carlo, approximate lookahead, entropy-guided proposals, distillation). We instead keep the sampler: Predictive SubTree Prefetching (PreSTO) completes multiple MH transitions per model call without changing the MH transition kernel. Future MH outcomes form a tree of accept/reject decisions; PreSTO builds a prefetching subtree of it, generates every proposal whose prefix is already available in one batched call, and follows the realized path with the original MH acceptance rule. Because MH reaches only a sparse, nearly unary part of each prefetched tree, we choose which decisions to prefetch under a budget by dynamic programming. On PowerMH and its follow-ups EntropyCut and MultiTryMH across 7 datasets and 5 base LLMs, PreSTO achieves median speedups of , , and , respectively; on the first two, it makes a median of fewer model calls, each only longer. Our predictive traversal rule improves the mean speedup over the default breadth-first traversal.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language models, power sampling, Markov chain Monte Carlo, inference-time acceleration

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_CtBJOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PreSTO accelerates MH-based LLM power sampling by batching suffix proposals for multiple possible future transitions. The method identifies which proposals can be generated before preceding accept/reject decisions are resolved. It further uses an acceptance predictor and dynamic programming to allocate the prefetch budget.

Critical strengths
  1. The paper is well motivated. Its main contribution is extending MCMC prefetching to autoregressive proposals by identifying which proposals can be generated in parallel based on their prefix dependencies and batching them.

  2. The experiments report median speedups of 1.71× over PowerMH and 1.88× over EntropyCut in cumulative model-call time across multiple models and datasets. The main results use BFS traversal, so the evidence for the batching method does not depend on the learned predictor.

  3. The paper is well written and organized. The figures clearly illustrate the method, and the tables summarize the experimental results effectively.

Critical weaknesses
  1. The efficiency evaluation uses fixed-length responses without EOS stopping and excludes scheduling overhead. This limits the evidence for end-to-end acceleration under natural stopping conditions.
Questions for authors
  1. All experiments use 1,024-token responses without EOS stopping. Do the reported speedups hold with natural EOS stopping under static batching (without continuous batching), where latency may be dominated by the longest proposal?

  2. Could you report end-to-end speedups, including the overhead of subtree construction, predictor inference, dynamic programming, etc.?

  3. Could you clarify how acceptance probabilities are computed for prefetched descendants? After accepting x→yx\to y, the next proposal zz should use A(z,y)A(z,y), but the inspected public code snapshot appears to use A(z,x)A(z,x). How does the implementation account for the actual current state?

2 comments
AuthorsOpenReview ↗

Replies to Reviewer CtBJ (Part 1)

Thank you for your valuable comments. We address your concerns blew including the new experimental results.


Q1: Natural EOS stopping under static batching

All experiments use 1,024-token responses without EOS stopping. Do the reported speedups hold with natural EOS stopping under static batching (without continuous batching), where latency may be dominated by the longest proposal?

We originally disabled EOS stopping to control for differences in early termination. We have now compared EOS-disabled and EOS-enabled runs: the table below is also in Section 5.2 (Case Study 7), p. 10, Table 4 of the revised paper.

Experiment setting: Qwen3.5-9B on the first 20 LCB V6 prompts, α=4\alpha=4, proposal temperature 0.25, K=100K=100, one block capped at 1,024 tokens, seed 10086, BFS at prefetch budgets 10 and 20; all six runs completed all 20 prompts.

Table 1: Sampler time and suffix length with and without EOS stopping.

α\alphaEnd-of-sentence (EOS)Prefetch budgetPowerMH sampler time (s)PreSTO sampler time (s)SpeedupPowerMH mean suffix length (tokens)PreSTO mean suffix length (tokens)
4Disabled10590.61±33.67590.61_{\pm 33.67}298.24±13.00298.24_{\pm 13.00}1.98×522.93633.38
4Disabled20590.61±33.67590.61_{\pm 33.67}260.41±32.51260.41_{\pm 32.51}2.27×522.93668.50
4Enabled10588.99±31.25588.99_{\pm 31.25}295.19±12.37295.19_{\pm 12.37}2.00×522.44633.38
4Enabled20588.99±31.25588.99_{\pm 31.25}262.58±32.65262.58_{\pm 32.65}2.24×522.44668.50

Conclusion: With EOS stopping enabled, our method still accelerates the baseline, by 2.00×2.00\times at budget 10 and 2.24×2.24\times at budget 20.


AuthorsOpenReview ↗

Replies to Reviewer CtBJ (Part 2)

Q2: Complete end-to-end time

Could you report end-to-end speedups, including the overhead of subtree construction, predictor inference, dynamic programming, etc.?

We have now measured the complete end-to-end time of a request for sequential PowerMH, PreSTO-BFS, and PreSTO-predictive, with every scheduling component timed separately: see Experiment E1 in main_rebuttal_experiment.md for the setting and the timer. The table below is Table 13 in Appendix E.6 (Case Study 6), p. 45 of the revised paper.

Experiment setting: Qwen3.5-9B on LCB V6, K=100K=100, with three seeds. Each entry is the time in seconds, with its percentage of the total request time in parentheses.

Table 2: End-to-end time breakdown for PowerMH and PreSTO.

MethodPrefetch budgetGeneration and scoringPredictionDynamic Programming computeSubtree managementTraversal and state updatesOther overheadTotal
Sequential PowerMH—566.578 (99.980%)———0.053 (0.009%)0.058 (0.010%)566.689
PreSTO-BFS4515.169 (99.973%)——0.011 (0.002%)0.080 (0.016%)0.046 (0.009%)515.306
PreSTO-BFS8461.296 (99.960%)——0.010 (0.002%)0.114 (0.025%)0.062 (0.013%)461.482
PreSTO-BFS10432.863 (99.951%)——0.010 (0.002%)0.132 (0.030%)0.072 (0.017%)433.077
PreSTO-BFS12416.837 (99.940%)——0.011 (0.003%)0.156 (0.037%)0.084 (0.020%)417.087
PreSTO-BFS16386.436 (99.921%)——0.012 (0.003%)0.192 (0.050%)0.102 (0.026%)386.741
PreSTO-BFS20365.518 (99.905%)——0.012 (0.003%)0.222 (0.061%)0.112 (0.031%)365.864
PreSTO-BFS32330.404 (99.845%)——0.016 (0.005%)0.324 (0.098%)0.172 (0.052%)330.916
PreSTO-predictive4378.097 (99.975%)0.003 (0.001%)0.005 (0.001%)0.006 (0.002%)0.050 (0.013%)0.030 (0.008%)378.190
PreSTO-predictive8332.211 (99.961%)0.004 (0.001%)0.008 (0.002%)0.006 (0.002%)0.073 (0.022%)0.040 (0.012%)332.342
PreSTO-predictive10321.435 (99.952%)0.004 (0.001%)0.011 (0.004%)0.007 (0.002%)0.085 (0.027%)0.045 (0.014%)321.588
PreSTO-predictive12303.981 (99.943%)0.005 (0.002%)0.014 (0.005%)0.007 (0.002%)0.097 (0.032%)0.051 (0.017%)304.156
PreSTO-predictive16293.749 (99.917%)0.007 (0.003%)0.028 (0.009%)0.008 (0.003%)0.128 (0.044%)0.073 (0.025%)293.992
PreSTO-predictive20276.947 (99.889%)0.009 (0.003%)0.046 (0.017%)0.009 (0.003%)0.153 (0.055%)0.089 (0.032%)277.254
PreSTO-predictive32268.565 (99.778%)0.019 (0.007%)0.182 (0.067%)0.012 (0.004%)0.237 (0.088%)0.148 (0.055%)269.162

Conclusion: LLM generation and scoring dominates the end-to-end time. It accounts for at least 99.78%99.78\% of every request, for PowerMH and for PreSTO under both traversal rules. All other components together take at most 0.22%0.22\% of the total time.


Q3: Acceptance against the actual current state

Could you clarify how acceptance probabilities are computed for prefetched descendants? After accepting x→yx\to y, the next proposal zz should use A(z,y)A(z,y), but the inspected public code snapshot appears to use A(z,x)A(z,x). How does the implementation account for the actual current state?

Thank you for checking the implementation in the anonymous snapshot. We have updated and verified the correctness of the anonymous snapshot in the function def batched_proposal_call(...) in src/power_sharpening/backends/vllm/samplers/proposal_llm_call.py, so that, after accepting x→y\mathbf{x}\to\mathbf{y}, the next proposal z\mathbf{z} is evaluated with A(z,y)A(\mathbf{z},\mathbf{y}).

Reviewer_6Y82OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces PreSTO (Predictive SubTree Prefetching), a framework for accelerating Metropolis–Hastings (MH)-based power sampling for large language models. Power sampling targets a sharpened sequence distribution and has been shown in prior work to improve reasoning without additional model training. However, sequential MH updates incur substantial latency because each proposal ordinarily depends on the preceding accept/reject decision.

PreSTO organizes future MH decisions into a prefetching subtree and batches feasible suffix-resampling proposals whose conditioning prefixes are already available. It then follows the realized path using the original acceptance rule. Proposition 1 establishes that, under assumptions A1–A3, PreSTO-PowerMH reproduces sequential PowerMH after the same number of committed transitions. To reduce speculative work on unlikely branches, a predictive traversal rule uses estimated epsilon-certainty class probabilities and dynamic programming to maximize the predicted number of completed transitions under a fixed request budget.

Across five backbones and seven datasets, the paper reports median speedups of 1.71× over PowerMH and 1.88× over EntropyCut in cumulative model-call time, primarily using the default BFS traversal. Predictive scheduling is evaluated separately on one model–dataset combination. Paired TOST tests establish equivalence in 29 of 34 comparisons of likelihood and confidence diagnostic means on the retained evaluation subsets. These measurements provide useful implementation evidence, but do not establish full end-to-end speedups or equivalence of the complete output distribution.

Critical strengths
  1. Kernel-preserving acceleration with a clear autoregressive feasibility condition. Condition 1 (p4) identifies when a future suffix proposal can be generated before its parent proposal is available, exploiting the shared-prefix structure of autoregressive sampling. Proposition 1 (p18–19) provides a convincing coupling argument for PreSTO-PowerMH under explicit assumptions covering correct proposal conditioning, preservation of independent random inputs across scheduling and deferral, and exact acceptance decisions. This is consequential because it accelerates the original finite-step sampler without introducing an additional sampling approximation. The TOST results provide complementary evidence of agreement in the evaluated diagnostic means; they do not independently verify the exact transition kernel or guarantee unchanged answer accuracy.

  2. Meaningful matched call-time gains and an informative account of speculative work. The PowerMH/EntropyCut comparisons match each sequential sampler with its own PreSTO implementation using the same backbone, initialization, parameters, prompts, and patched vLLM backend, with prefix caching enabled for both. Figure 5 (p7) illustrates the mechanism on LCB V6 with Qwen3.5-9B: cumulative PowerMH model-call time decreases from 481.02±27.14 to 253.29±23.12 seconds, approximately a 1.90× improvement, because fewer calls outweigh longer individual calls. Table 2 (p8) also discloses increased uncached prefix work per transition, distinguishing latency savings from reduced computation. The predictive DP is a principled optimization of a specified transition-count surrogate, offering a coherent approach to allocating expensive speculative requests rather than expanding all branches uniformly.

Critical weaknesses
  1. Incomplete end-to-end cost accounting limits the practical interpretation of the speedups. Appendix D.4 (p26) explicitly states that the PowerMH/EntropyCut acceleration measurements cover model calls only, excluding subtree management, traversal, and other system overhead. The exposed costs of the predictor and DP solver are not clearly broken down. Consequently, the magnitude of full-request acceleration remains uncertain, particularly as the prefetch budget grows. This matters because fewer serial calls are only practically beneficial if their savings exceed the complete scheduling and speculative-execution costs. The MultiTryMH results should also be interpreted separately: Table 8 (p34) uses different timing boundaries and rescoring/score-reuse conditions, with unmatched completed prompt sets in some rows, rather than isolating prefetching under fully matched conditions.

  2. Validation of predictive scheduling and its generalization is limited. The predictive-versus-BFS comparison in Figure 7 (p9) is restricted to LCB V6 with Qwen3.5-9B. Although predictive traversal improves the mean speedup in all six configurations, three improvements lie within one standard deviation of cumulative time. Appendix E.4 (p36–37) evaluates logistic classifiers as linear baselines for the learned predictor and finds cut position to be the strongest feature; the predictor actually deployed in Figure 7, its calibration, and its independent training/evaluation protocol need clearer specification. More broadly, the main speed experiments use the first 20 prompts per dataset, a single seed, a fixed exponent, and one 1,024-token block with EOS ignored; the MMLU subset consists only of abstract-algebra questions. These restrictions do not invalidate the measured gains, but limit claims of robust generalization to natural-length or unfamiliar workloads. Prediction errors may reduce scheduling efficiency; they should not be assumed to alter the sampling law when the kernel-preservation assumptions and exact acceptance rules remain satisfied.

Questions for authors
  1. End-to-end costs and fair comparison. Please report complete end-to-end latency, separating generation, prediction, DP, subtree management, and traversal. How do these costs scale with the prefetch budget (NpfN_{\mathrm{pf}}), and do the reported PowerMH/EntropyCut gains remain after including all exposed overhead? For MultiTryMH, can you provide a comparison using identical completed prompts, identical score-reuse optimizations, and the same timing boundary?

  2. Predictor specification and robustness. Please specify the predictor actually used in Figure 7, including its inputs, architecture, training/validation split, and probability calibration, and explain its relationship to the logistic baselines in Appendix E.4. How does predictive allocation compare with BFS under distribution shift or deliberately degraded predictions, in both completed transitions per call and full end-to-end latency? Representative cross-model/dataset or sequence-length checks, with repeated-run uncertainty estimates, would materially clarify the generality and practical value of predictive scheduling.

5 comments
AuthorsOpenReview ↗

Replies to Reviewer 6Y82 (Part 1)

Thank you for your valuable comments. We would like to address your concerns below, including the new experimental results.


Q1: End-to-end costs and fair comparison

Please report complete end-to-end latency, separating generation, prediction, DP, subtree management, and traversal. How do these costs scale with the prefetch budget (Npf), and do the reported PowerMH/EntropyCut gains remain after including all exposed overhead? For MultiTryMH, can you provide a comparison using identical completed prompts, identical score-reuse optimizations, and the same timing boundary?

  1. For end-to-end cost, we have measured the full time of a request for the sequential samplers, PreSTO-BFS, and PreSTO-predictive on the same prompts and seeds, at prefetch budgets 4 to 32. The results are in Tables 1, 2-1, and 2-2 of our shared response to all reviewers (the top-level comment); the two breakdowns are also Tables 13 and 14 in Appendix E.6 (Case Study 6), pp. 45–46 of the revised paper.

    • For both PowerMH and EntropyCut, LLM generation and scoring takes at least 99.7%99.7\% of the end-to-end time at every budget; all other computation together takes less than 0.3%0.3\% (Tables 2-1 and 2-2 of the shared response).
    • The gains persist at every budget with all costs included: PreSTO is 1.04×1.04\times to 2.04×2.04\times faster than PowerMH and 1.22×1.22\times to 2.75×2.75\times faster than EntropyCut (Table 1 of the shared response).
  2. For MultiTryMH, we previously report result with our own implementation of the method, written to the best of our understanding. The code of its recently published version (Guo et al., 2026) has since been released, so we now follow it for a fair comparison. The results are in Table 3 of our shared response to all reviewers.

Under matched conditions, PreSTO-MultiTryMH is 1.15×1.15\times to 1.24×1.24\times faster than sequential MultiTryMH at prefetch budgets 20 to 50, and fastest at budget 20 (Table 3 of the shared response).

Because these runs are computationally expensive, the MultiTryMH results in Table 1 of the paper are not yet updated. We will update them, for all datasets and base LLMs, in the next revision.

AuthorsOpenReview ↗

Replies to Reviewer 6Y82 (Part 2)

Q2: Predictor specification

Please specify the predictor actually used in Figure 7, including its inputs, architecture, training/validation split, and probability calibration, and explain its relationship to the logistic baselines in Appendix E.4.

For the predictor specification, please see Appendix E.7 (Case Study 8), pp. 46–48 of the revised paper. In summary:

  1. For its inputs and architecture, the predictor in Figure 7 is a three-class logistic regression whose only input is the cut fraction cj/Tc_j/T.

  2. For its relationship to the logistic baselines, the predictor is one of them: the cut-fraction row of Table 1 below, in italics. There is no separate learned model; the other rows, which add features or hidden layers, are alternatives that we evaluated and do not use.

  3. For its calibration, we report the log loss on held-out prompts: the predictor lowers it from 0.9400.940, the class-frequency baseline, to 0.8190.819 for PreSTO-PowerMH, and from 0.9540.954 to 0.8840.884 for PreSTO-EntropyCut (Table 15, p. 48).

  4. For the training and evaluation split, the scores in Table 1 below come from five-fold cross-validation with whole prompts held out. The predictor is then refit on all 4,621 nodes of that run, which uses the first 20 LCB V6 prompts. The independent test is the reference row of Table 2 in Q3: the predictor is fitted on prompts 20 to 39, frozen, and tested on prompts 0 to 19, where predictive traversal is 1.30×1.30\times faster than BFS.

Experiment setting: Qwen3.5-9B on the first 20 LCB V6 prompts, one run per sampler; the examples are the prefetched nodes (4,621 for PreSTO-PowerMH and 4,533 for PreSTO-EntropyCut), labeled at ϵ=0.01\epsilon=0.01. Each classifier is evaluated by five-fold cross-validation with whole prompts held out. The constant baseline predicts the majority class. Italics mark the configuration we use; NA means not available.

Table 1: Prediction of the ϵ\epsilon-certainty class (Table 15 of the revised paper).

ConfigurationPreSTO-PowerMH: accuracy ↑PreSTO-EntropyCut: accuracy ↑
Constant baseline0.6090.596
(a) Feature sets, logistic regression
Cut fraction0.6430.625
Tree position0.6470.627
Likelihood0.6120.596
EntropyNA0.596
Cut fraction + tree position0.6470.627
Cut fraction + likelihood0.6390.631
Cut fraction + entropyNA0.636
Tree position + likelihood0.6430.631
Tree position + entropyNA0.633
Likelihood + entropyNA0.596
Cut fraction + tree position + likelihood0.6430.631
All four featuresNA0.626
(b) Hidden layers, cut fraction only
None (logistic regression)0.6430.625
160.6480.625
320.6460.633
640.6460.616
32–320.6530.637
64–640.6540.621

Conclusion. The cut-only logistic regression improves on the constant baseline for both samplers: accuracy rises from 0.6090.609 to 0.6430.643 for PreSTO-PowerMH and from 0.5960.596 to 0.6250.625 for PreSTO-EntropyCut. No other feature set or hidden-layer configuration improves on it by more than 0.0120.012 in accuracy, so we use the simplest model.

AuthorsOpenReview ↗

Replies to Reviewer 6Y82 (Part 3)

Q3: Robustness to distribution shift and degraded predictions

How does predictive allocation compare with BFS under distribution shift or deliberately degraded predictions, in both completed transitions per call and full end-to-end latency?

We freeze one predictor and reuse it unchanged on every workload in Table 2. All six shifted workloads are fully timed; for the two degraded workloads we report transitions per call and model calls per request.

Experiment setting: The predictor is fitted on LCB V6 prompts 20 to 39 with Qwen3.5-9B and then frozen. The reference setting is LCB V6 prompts 0 to 19 with Qwen3.5-9B, prefetch budget 20, K=100K=100, α=4\alpha=4, one 1,024-token block, and three seeds; each shifted row changes one of these factors. The two degraded rows keep the reference workload and its BFS runs, and either mix the predictions half-and-half with a uniform prior or permute them across nodes. Accuracy is that of the frozen predictor on the prefetched nodes of each workload, against a baseline that predicts the workload's majority class. Each timed row uses 60 matched requests and reports the end-to-end time as mean ± standard deviation over the three seeds.

Table 2: The frozen predictor under distribution shift and degraded predictions.

Test workloadBaseline accuracyPredictor accuracyTransitions per call, BFSTransitions per call, predictiveEnd-to-end time (s), BFSEnd-to-end time (s), predictiveSpeedup over BFS
Reference (no shift)
LCB V6, Qwen3.5-9B0.7310.7315.26.9362.0 ± 7.5279.4 ± 13.11.30×
Shift: dataset
MATH5000.6960.6965.06.2317.2 ± 11.9250.9 ± 11.71.26×
MMLU0.4360.2662.42.4657.1 ± 17.5645.9 ± 47.41.02×
Shift: base model
Qwen3.5-4B0.7390.7395.16.8251.0 ± 14.0196.1 ± 12.01.28×
Gemma4-12B-it0.4100.4103.64.0658.9 ± 41.1572.7 ± 19.81.15×
Shift: block length
512-token block0.6960.6965.06.3168.2 ± 3.5131.4 ± 2.71.28×
Shift: sharpening exponent
α=2\alpha=20.7030.7035.16.9317.8 ± 7.9231.7 ± 11.51.37×
Degraded predictions
Mixed with a uniform prior0.7310.7315.26.3———
Permuted across nodes0.7310.7315.26.7———

Conclusion.

  1. For distribution shift, predictive traversal with the frozen predictor is faster than BFS on five of six shifted workloads (1.15×1.15\times to 1.37×1.37\times; reference 1.30×1.30\times) and matches it on MMLU (1.02×1.02\times), where the predictor's accuracy falls below the baseline (0.2660.266 against 0.4360.436).

  2. For degraded predictions, predictive traversal still completes more transitions per call than BFS: 6.36.3 with the probabilities mixed half-and-half with a uniform prior and 6.76.7 with the predictions permuted across nodes, against 5.25.2 for BFS and 6.96.9 with the intact predictor.

  3. For latency, since generation and scoring take at least 99.7%99.7\% of a request (Q1), we compare model calls: a request needs 19.2519.25 model calls under BFS, 15.7715.77 with the mixed predictor, 14.9214.92 with the permuted one, and 14.5514.55 with the intact one.

  4. For the effect of prediction errors, they change the speed only and do not alter the sampling law. The predictions decide which requests are prefetched, and every accept or reject decision still uses the exact MH rule.

  5. For an illustration of the comparison with BFS, please see Figure 7(d), p. 9, which shows the first prefetched subtree of one prompt under each traversal rule at five budgets. Table 2 above gives the averages.

Reviewer_6tGKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper speeds up PowerMH, a Metropolis–Hastings (MH) sampler for power sampling from p0αp_0^\alpha, by applying MCMC prefetching. Future accept/reject outcomes form a binary tree; the key observation (Condition 1) is that whenever a child's cut index is no larger than its parent's, its suffix proposal depends only on a prefix of the current state, allowing all such proposals to be generated in a single batched vLLM call with prefix caching before walking the realized path under the standard MH acceptance rule. By a coupling argument (Proposition 1), this preserves the exact PowerMH transition kernel. Observing that most acceptance probabilities are close to 0 or 1—making the reachable subtree sparse and nearly unary—the authors further propose a predictive traversal rule that allocates the prefetch budget via a Sequoia-style dynamic program driven by a logistic regression predictor on the cut position. Experiments evaluate PreSTO on PowerMH, EntropyCut, and MultiTryMH across five 4B–12B models and seven datasets (first 20 prompts each, one 1,024-token block, K=100K = 100, α=4\alpha = 4, single H100), reporting median model-call speedups of 1.71× (PowerMH) and 1.88× (EntropyCut), TOST equivalence on base-model likelihood and confidence diagnostics, and modest KV-cache overhead.

Critical strengths

The method is exact by construction for PowerMH, which matters here because the whole point of power sampling is sampling from the sharpened target distribution: unlike SMC or lookahead approximations, PreSTO only changes when proposals are computed, so downstream task accuracy reported for PowerMH carries over without re-validation. Condition 1 is a clean, sound observation that makes MCMC prefetching feasible for autoregressive suffix resampling. Moreover, the evaluation is broad across models and datasets and transparent about where the speedup comes from: decomposing wall-clock call time into fewer calls versus longer calls (Figure 1, Case Study 1) clearly shows that a 20-request batch costs roughly 2×2\times a single request on this hardware, and Table 2 openly reports that uncached tokens per transition increase by 1.5×1.5\times to 4.4×4.4\times. Finally, the vLLM patch returning log⁡qτ\log q_\tau, log⁡p0\log p_0, and token entropy in a single forward pass is a useful standalone engineering contribution for anyone implementing these samplers.

Critical weaknesses

First, the speedups are measured in a regime unusually favorable to prefetching and may not transfer to realistic serving workloads. Every experiment runs a single chain at a time on an H100, so the baseline issues batch-size-1 decode calls that leave the GPU largely underutilized, allowing PreSTO to fill that idle capacity with speculative proposals even though only ~4 of 20 per call land on the realized path. Moreover, the headline metric covers cumulative model-call time only (excluding tree construction, DP, and traversal); the benchmark uses a single 1,024-token block with K=100K = 100 and no EOS stopping rather than the block-by-block schedule of Karan & Du (2026) with fewer MH steps per block; and α\alpha is fixed at 44, even though the near-deterministic acceptances that keep the tree sparse likely stem from a large α\alpha and long resampled suffixes. Without measurements batching multiple prompts or chains concurrently, under the original multi-block schedule, in end-to-end wall-clock time, and at smaller α\alpha, it remains unclear whether PreSTO delivers a general throughput speedup or mainly a latency gain for isolated queries.Second, two of the three headline claims are weaker than presented. For MultiTryMH, the comparison (2.33×2.33\times median in the abstract, up to 8.1×8.1\times) pits full MultiTryMH steps with candidate rescoring against a PreSTO variant that skips rescoring, with several rows computed from incomplete runs over mismatched prompt subsets (e.g., n=17/1n = 17/1), so this figure should not be in the abstract. For EntropyCut, the remark following Proposition 1 asserts exactness, yet Appendix E.1 notes that kernel preservation still needs verification, and it is unclear how an acceptance child's cut index can be sampled from the EntropyCut distribution before its parent's suffix—whose token entropies define that law—has even been generated.Finally, on novelty, MCMC prefetching with predicted branch probabilities dates back to Angelino et al. (2014), and the budget-allocation DP follows Sequoia. Thus, the new contribution lies in Condition 1 and the vLLM implementation—a solid systems contribution, though incremental in scope.

Questions for authors

(1) For PreSTO-EntropyCut, how is the cut index of an acceptance child drawn, given that the EntropyCut cut distribution depends on the entropies of the parent's new suffix, which only exist after the batched call? If the root state's entropies or a truncated law are used instead, the kernel changes, and the answer would change how I weigh the EntropyCut results. (2) The pooled PowerMH differences are small, but their 90% intervals exclude zero (+0.038 SD in log-likelihood, +0.061 SD in confidence), while under an exact kernel the expected difference is zero. Does MHTRANSITION stop at exactly K in the last round, or can PreSTO run past K? Since Proposition 1 is a coupling argument, a direct check is also possible: with shared per-decision random inputs and batch-invariant kernels, do the two samplers produce identical trajectories? That would be much stronger evidence than TOST on two summary statistics. (3) What is the throughput (transitions per second, or prompts per GPU hour) for both methods when 8 or 32 prompts run concurrently, and what is the end-to-end wall-clock including tree construction, the DP and traversal? (4) How do the speedups change under the original multi-block PowerMH schedule with EOS stopping, and for a smaller α such as 2? (5) How does BFS compare with prefetching only the rejection spine from the current state (static prefetching as in Strid, 2010), which is simpler and also exact? As suggestions rather than requirements: the predictive rule is fit and evaluated only on LCB V6 with Qwen3.5-9B and is within one SD of BFS in 3 of the 6 settings, so showing that it transfers to other models and datasets would make that part convincing, and reporting task accuracy once would be a cheap sanity check of the implementation.

5 comments
AuthorsOpenReview ↗

Replies to Reviewer 6tGK (Part 1)

Thank you for your valuable comments. We address your concerns below, including the new experimental results.


Q1: Original multi-block schedule, EOS stopping, and α=2\alpha=2

How do the speedups change under the original multi-block PowerMH schedule with EOS stopping, and for a smaller α such as 2?

We have now run the original multi-block schedule (16 blocks of 192 tokens, 10 MH steps per block) in all four conditions; the table below gives the results, and its main numbers are also in Table 16 in Appendix E.8 (Case Study 9), p. 48 of the revised paper.

Experiment setting: Qwen3.5-9B on LCB V6, prefetch budget 20, 20 prompts and three seeds (10086, 10087, and 10088).

Table 1: Benchmark under multi-block schedule.

MeasurementEOS off, α=4\alpha=4EOS on, α=4\alpha=4EOS off, α=2\alpha=2EOS on, α=2\alpha=2
PowerMH end-to-end time (s)1254.51266.31262.61270.8
PreSTO-BFS end-to-end time (s)805.6842.1822.0831.3
Speedup1.56×1.50×1.54×1.53×
Mean final response length (tokens; PowerMH / PreSTO)3072.0 / 3072.03072.0 / 3072.03072.0 / 2995.23072.0 / 3072.0
Mean generated suffix length (tokens; PowerMH / PreSTO)817.0 / 956.6818.3 / 970.1816.6 / 962.3819.0 / 964.0
Mean longest suffix per static batch (tokens; PowerMH / PreSTO)817.0 / 1405.0818.3 / 1414.3816.6 / 1401.8819.0 / 1397.8
Mean executed blocks per request (PowerMH / PreSTO)16.00 / 16.0016.00 / 16.0016.00 / 16.0016.00 / 16.00
Mean committed MH transitions per request (PowerMH / PreSTO)160.0 / 160.0160.0 / 160.0160.0 / 160.0160.0 / 160.0
Committed MH transitions per model call (PowerMH / PreSTO)1.00 / 4.051.00 / 3.941.00 / 4.031.00 / 3.93
Useful/generated proposal fraction (PreSTO)0.2860.2840.2860.283
Epsilon-certain committed decisions (%; PowerMH / PreSTO)93.6 / 95.094.0 / 94.790.8 / 91.490.9 / 91.4
Task-correct responses per seed, of 20 (PowerMH / PreSTO)7, 5, – / –, 6, 67, 7, 6 / 6, 7, 5–, 7, 7 / 7, 5, 77, –, 6 / 7, 6, 6
Completed / requested requests (PowerMH / PreSTO)40/60 / 40/6060/60 / 60/6040/60 / 60/6040/60 / 60/60
Matched (prompt, seed) pairs20604040

Conclusion.

  1. For the multi-block schedule, PreSTO-BFS at budget 20 is faster than sequential PowerMH end-to-end in all four conditions, by 1.50×1.50\times to 1.56×1.56\times. With 10 transitions per block, PreSTO commits about 4 transitions per model call (3.93 to 4.05), against 5.2 in the single-block setting.

  2. For EOS stopping, enabling it changes the speedup little: from 1.56×1.56\times to 1.50×1.50\times at α=4\alpha=4 and from 1.54×1.54\times to 1.53×1.53\times at α=2\alpha=2. No request stopped early: every request executed all 16 blocks and returned 3,072 tokens, so these runs do not yet show the effect of natural-length responses.

  3. For α=2\alpha=2, the speedup is close to that at α=4\alpha=4: 1.54×1.54\times against 1.56×1.56\times with EOS off, and 1.53×1.53\times against 1.50×1.50\times with EOS on.

  4. For the difference from the single-block setting, on the same GPU model the multi-block speedup is 1.42×1.42\times at α=4\alpha=4, against 1.50×1.50\times for a single block.

AuthorsOpenReview ↗

Replies to Reviewer 6tGK (Part 2)

Q2: Fairness of the MultiTryMH headline comparison

The MultiTryMH comparison pits full MultiTryMH steps including candidate rescoring against a PreSTO version that skips rescoring, and many rows come from incomplete runs over different prompt sets...

Thank you for pointing this out. The submitted paper used our own implementation of MultiTryMH, written to the best of our understanding, because no official code had been released at that time. The code of its recently published version (Guo et al., 2026) has since been released, so we now follow it and have run a matched comparison: see Table 3 of our shared response to all reviewers.

  1. For the result, under these matched conditions, PreSTO-MultiTryMH is 1.15×1.15\times to 1.24×1.24\times faster than sequential MultiTryMH at prefetch budgets 20 to 50, and fastest at budget 20.

  2. We will update the MultiTryMH results in Table 1 and the abstract in the next revision, because these runs take a large amount of time to run.


Q3: EntropyCut cut selection and the scope of exactness

For PreSTO-EntropyCut, how is the cut index of an acceptance child drawn, given that the EntropyCut cut distribution depends on the entropies of the parent's new suffix, which only exist after the batched call? If the root state's entropies or a truncated law are used instead, the kernel changes, and the answer would change how I weigh the EntropyCut results.

We have extended the exactness result to EntropyCut: see the remark after Proposition 1 (Appendix B.2, pp. 21–22) of the revised paper.

PreSTO-EntropyCut is exact in two cases:

  1. Under the rejection-spine traversal, for any β\beta, because all of its decisions are made at the same state.
  2. At β=0\beta=0, under any traversal rule, because the cut law is then uniform.

For β>0\beta>0 under a general traversal rule, such as BFS or predictive traversal, PreSTO-EntropyCut is an approximation and exactness does not hold. These rules also prefetch decisions that follow an acceptance, and such a decision draws its cut from the cut law of the batch root, not from that of its own state.


Q4: Exactly KK transitions, nonzero diagnostic differences, and direct coupling

The pooled PowerMH differences are small, but their 90% intervals exclude zero (+0.038 SD in log-likelihood, +0.061 SD in confidence), while under an exact kernel the expected difference is zero. Does MHTRANSITION stop at exactly K in the last round, or can PreSTO run past K? Since Proposition 1 is a coupling argument, a direct check is also possible: with shared per-decision random inputs and batch-invariant kernels, do the two samplers produce identical trajectories? That would be much stronger evidence than TOST on two summary statistics.

  1. stop at exactly KK transitions? Yes: see Appendix B, p. 20 of the revised paper.

  2. Do shared per-decision random inputs yield identical trajectories? In theory, yes (Proposition 1). On a real serving engine, not in general.

    The two samplers batch their requests differently, and batched GPU inference is not bitwise invariant to batch composition: a near-tie between two tokens can flip one sampled token, after which the trajectories diverge. Exactness therefore means the same output distribution, not the same trajectories.

  3. diagnostic differences whose intervals exclude zero? The TOST tests equivalence within the margin δ=0.2\delta=0.2 SD, not equality to zero.

    The pooled PowerMH differences (+0.038+0.038 SD in log-likelihood, +0.061+0.061 SD in confidence) exclude zero but lie well inside ±0.2\pm0.2 SD, so equivalence holds. At the pair level, every simultaneous 90% interval includes zero (Figure 15, Appendix E.3, p. 40).


Q5: Contribution relative to MCMC prefetching and Sequoia

On novelty, prefetching with predicted branch probabilities goes back to Angelino et al. (2014) and the budget DP follows Sequoia, so what is new is Condition 1 and the LLM implementation; that is a reasonable systems contribution, but a modest one.

Section 4 discusses our contributions relative to MCMC prefetching and Sequoia. We summarize the key distinctions below.

  1. Contribution relative to MCMC prefetching.

    • In the LLM setting, constructing the full binary candidate tree of Angelino et al. (2014) is expensive, as generating the proposals is itself the most costly part of the sampler.

    • Our method instead selects a subset of proposals that can be generated in one batch, trading off MH progress against sampling time.

  2. Contribution relative to Sequoia.

    • Sequoia addresses tree-based speculative decoding, whereas PreSTO addresses MCMC prefetching. The two methods operate in different computational settings.

    • Our dynamic program derivation in Appendix C.4, p. 27 is inspired by Sequoia paper, and we acknowledge this connection there.

AuthorsOpenReview ↗

Replies to Reviewer 6tGK (Part 3)

Q6: Rejection-spine baseline

How does BFS compare with prefetching only the rejection spine from the current state (static prefetching as in Strid, 2010), which is simpler and also exact?

We have implemented the rejection-spine baseline with the same proposal-generation and MH-scoring code as PreSTO: see Appendix E.4 (Case Study 4), p. 41 of the revised paper for its definition. The table below gives the results and is also Table 12(b), p. 41, there.

Experiment setting: Qwen3.5-9B on the first 4 LCB V6 prompts, α=4\alpha=4, 20 committed MH transitions, one 1,024-token block, EOS disabled, seed 10086. End-to-end time is the mean time of one request in seconds, from the start of the initial generation to the returned sample. "Speedup over rejection spine" is the rejection-spine end-to-end time divided by the rule's end-to-end time at the same budget. Transitions per call counts the committed MH transitions per refinement model call.

Table 2: Rejection spine, BFS, and predictive traversal in a short run.

Prefetch budgetTraversal ruleEnd-to-end time (s)Speedup over rejection spineTransitions per call
8Rejection spine101.61.00×3.48
8BFS120.80.84×3.08
8Predictive99.41.02×3.64
10Rejection spine109.91.00×3.33
10BFS125.60.87×3.20
10Predictive117.00.94×3.20
12Rejection spine110.31.00×3.48
12BFS124.60.89×3.33
12Predictive105.81.04×3.64
16Rejection spine128.31.00×3.20
16BFS120.01.07×3.81
16Predictive94.81.35×4.71
20Rejection spine120.81.00×3.64
20BFS134.60.90×3.48
20Predictive100.81.20×4.71

Conclusion. From fastest to slowest, the ranking is predictive traversal, the rejection spine, and BFS: averaged over the five budgets, a request takes 103.6 s, 114.2 s, and 125.1 s.

This order holds at three of the five budgets; the rejection spine is fastest at budget 10, and BFS is second at budget 16.


Q7: Predictor transfer and task-accuracy sanity check

As suggestions rather than requirements: the predictive rule is fit and evaluated only on LCB V6 with Qwen3.5-9B and is within one SD of BFS in 3 of the 6 settings, so showing that it transfers to other models and datasets would make that part convincing, and reporting task accuracy once would be a cheap sanity check of the implementation.

  1. For predictor transfer, we reuse the frozen predictor (fitted on LCB V6 with Qwen3.5-9B) and compare predictive traversal with BFS at budget 20 on six shifted workloads, with 60 matched requests each. Predictive traversal is faster than BFS on five of them: MATH500 (1.26×1.26\times), Qwen3.5-4B (1.28×1.28\times), Gemma4-12B-it (1.15×1.15\times), a 512-token block (1.28×1.28\times), and α=2\alpha=2 (1.37×1.37\times), against 1.30×1.30\times in the reference setting (LCB V6, Qwen3.5-9B). On MMLU, where the predictor transfers poorly, it matches BFS (1.02×1.02\times). Predictions only decide which requests are prefetched, so a poor predictor can reduce the speedup but cannot change the samples.

  2. For task accuracy, the table below gives the matched counts, including new counts at K=100K=100.

Experiment setting: The same 20 LCB V6 prompts with Qwen3.5-9B. The rows with K≤30K\le30 use one seed and report the sampler-time ratio. The rows with K=100K=100 come from the end-to-end runs of our shared response (Table 1 there): three seeds, 60 matched requests, and the end-to-end time ratio. The accuracy difference is PreSTO minus PowerMH. The exact McNemar p-value is 1 in every row.

Table 3: Task accuracy of PowerMH and PreSTO-BFS on matched prompts.

KPrefetch budgetPowerMH correctPreSTO correctAccuracy differenceTime ratio
10104/203/20-0.051.36×
20104/204/200.001.60×
30104/203/20-0.051.82×
1001010/6010/600.001.25×
1002010/6010/600.001.50×

Comments on the paper

4 comments
AuthorsOpenReview ↗

Replies to all reviewers (Part 1)

Q1: End-to-end time with all scheduling costs included

Reviewer 6Y82: Please report complete end-to-end latency, separating generation, prediction, DP, subtree management, and traversal. How do these costs scale with the prefetch budget (Npf), and do the reported PowerMH/EntropyCut gains remain after including all exposed overhead?

Reviewer CtBJ: Could you report end-to-end speedups, including the overhead of subtree construction, predictor inference, dynamic programming, etc.?

Reviewer 6tGK: What is the throughput (transitions per second, or prompts per GPU hour) for both methods when 8 or 32 prompts run concurrently, and what is the end-to-end wall-clock including tree construction, the DP and traversal?

We have now measured the complete end-to-end time of a request for the sequential samplers, PreSTO-BFS, and PreSTO-predictive on the same prompts and seeds, with every scheduling component timed separately. The component breakdowns (Tables 2-1 and 2-2 below) are Tables 13 and 14 in Appendix E.6 (Case Study 6), pp. 45–46 of the revised paper.

Experiment setting: Qwen3.5-9B on 20 LCB V6 prompts with three seeds (60 matched requests per method), α=4\alpha=4, proposal temperature 1/α1/\alpha, K=100K=100, one 1,024-token block, EOS stopping disabled, one NVIDIA H100; EntropyCut uses β=4\beta=4. The predictor is fitted on 20 separate prompts and frozen. One timer encloses each request, from the start of the initial generation to the returned final sample; it excludes model loading, offline predictor fitting, output decoding, and grading.

Table 1: End-to-end request time and speedup over the sequential sampler. Each entry is the mean request time in seconds / speedup. The sequential samplers take 543.1 s (PowerMH) and 596.5 s (EntropyCut).

Prefetch budgetPowerMH + BFSPowerMH + predictiveEntropyCut + BFSEntropyCut + predictive
4524.0 / 1.04×374.9 / 1.45×488.3 / 1.22×339.4 / 1.76×
8459.7 / 1.18×327.9 / 1.66×450.7 / 1.32×295.2 / 2.02×
10433.7 / 1.25×318.6 / 1.70×401.7 / 1.48×273.4 / 2.18×
12414.0 / 1.31×299.7 / 1.81×390.0 / 1.53×267.3 / 2.23×
16385.9 / 1.41×295.7 / 1.84×363.4 / 1.64×247.8 / 2.41×
20362.0 / 1.50×279.4 / 1.94×341.2 / 1.75×239.5 / 2.49×
32331.5 / 1.64×266.3 / 2.04×319.3 / 1.87×217.2 / 2.75×

Conclusion. With every cost included, our method remains faster than the sequential sampler at every budget. For PowerMH, the speedup is 1.04×1.04\times to 1.64×1.64\times under BFS and 1.45×1.45\times to 2.04×2.04\times under predictive traversal. For EntropyCut, it is 1.22×1.22\times to 1.87×1.87\times under BFS and 1.76×1.76\times to 2.75×2.75\times under predictive traversal. Our validation shows that the evaluated prefetched EntropyCut code does not yet draw every cut from the actual current state's law, so we report the EntropyCut entries as cost measurements of that code.

AuthorsOpenReview ↗

Replies to all reviewers (Part 2-1)

Q2: Component breakdown of the end-to-end time

Experiment setting: The PowerMH runs of Table 1 (60 matched requests per method), with every phase inside the request timer timed separately, so the components sum to the total. Generation and scoring covers every model call: the initial generation and all proposals, used or not. Subtree management covers candidate collection, tree construction, and request construction. Traversal and state updates covers the cut draws, the acceptance tests, the tree walk, and the state updates. Other overhead is the remainder of the timer. "—" marks a component that the method does not have.

Table 2-1: End-to-end time breakdown for PowerMH and PreSTO. Each entry is the time in seconds, with its percentage of the total request time in parentheses.

MethodPrefetch budgetGeneration and scoringPredictionDynamic Programming computeSubtree managementTraversal and state updatesOther overheadTotalSpeedup
Sequential PowerMH—542.990 (99.984%)———0.040 (0.007%)0.046 (0.008%)543.077—
PreSTO-BFS4523.835 (99.974%)——0.011 (0.002%)0.078 (0.015%)0.046 (0.009%)523.9701.04×
PreSTO-BFS8459.486 (99.960%)——0.010 (0.002%)0.114 (0.025%)0.062 (0.013%)459.6721.18×
PreSTO-BFS10433.454 (99.951%)——0.010 (0.002%)0.132 (0.030%)0.072 (0.017%)433.6681.25×
PreSTO-BFS12413.745 (99.940%)——0.011 (0.003%)0.154 (0.037%)0.083 (0.020%)413.9931.31×
PreSTO-BFS16385.563 (99.921%)——0.012 (0.003%)0.191 (0.049%)0.102 (0.026%)385.8681.41×
PreSTO-BFS20361.650 (99.905%)——0.012 (0.003%)0.220 (0.061%)0.111 (0.031%)361.9931.50×
PreSTO-BFS32330.959 (99.846%)——0.016 (0.005%)0.325 (0.098%)0.171 (0.052%)331.4711.64×
PreSTO-predictive4374.758 (99.975%)0.003 (0.001%)0.005 (0.001%)0.006 (0.002%)0.049 (0.013%)0.029 (0.008%)374.8501.45×
PreSTO-predictive8327.763 (99.961%)0.003 (0.001%)0.008 (0.002%)0.006 (0.002%)0.072 (0.022%)0.039 (0.012%)327.8921.66×
PreSTO-predictive10318.457 (99.952%)0.004 (0.001%)0.011 (0.003%)0.006 (0.002%)0.085 (0.027%)0.045 (0.014%)318.6091.70×
PreSTO-predictive12299.562 (99.943%)0.005 (0.002%)0.014 (0.005%)0.007 (0.002%)0.096 (0.032%)0.050 (0.017%)299.7341.81×
PreSTO-predictive16295.421 (99.916%)0.007 (0.002%)0.028 (0.009%)0.008 (0.003%)0.130 (0.044%)0.074 (0.025%)295.6691.84×
PreSTO-predictive20279.124 (99.888%)0.009 (0.003%)0.047 (0.017%)0.009 (0.003%)0.156 (0.056%)0.091 (0.033%)279.4361.94×
PreSTO-predictive32265.663 (99.777%)0.019 (0.007%)0.182 (0.068%)0.012 (0.005%)0.235 (0.088%)0.148 (0.056%)266.2582.04×
AuthorsOpenReview ↗

Replies to all reviewers (Part 2-2)

Experiment setting: The EntropyCut runs of Table 1 (60 matched requests per method), with the same components as Table 2-1.

Table 2-2: End-to-end time breakdown for EntropyCut and PreSTO. Each entry is the time in seconds, with its percentage of the total request time in parentheses.

MethodPrefetch budgetGeneration and scoringPredictionDynamic Programming computeSubtree managementTraversal and state updatesOther overheadTotalSpeedup
Sequential EntropyCut—596.387 (99.974%)———0.096 (0.016%)0.059 (0.010%)596.542—
PreSTO-BFS4488.071 (99.963%)——0.027 (0.006%)0.106 (0.022%)0.046 (0.009%)488.2501.22×
PreSTO-BFS8450.487 (99.944%)——0.026 (0.006%)0.153 (0.034%)0.072 (0.016%)450.7381.32×
PreSTO-BFS10401.460 (99.936%)——0.023 (0.006%)0.166 (0.041%)0.069 (0.017%)401.7191.48×
PreSTO-BFS12389.695 (99.926%)——0.025 (0.006%)0.185 (0.047%)0.078 (0.020%)389.9831.53×
PreSTO-BFS16363.031 (99.905%)——0.026 (0.007%)0.223 (0.061%)0.095 (0.026%)363.3761.64×
PreSTO-BFS20340.758 (99.883%)——0.027 (0.008%)0.259 (0.076%)0.113 (0.033%)341.1581.75×
PreSTO-BFS32318.709 (99.818%)——0.034 (0.011%)0.372 (0.117%)0.175 (0.055%)319.2901.87×
PreSTO-predictive4339.261 (99.966%)0.002 (0.001%)0.018 (0.005%)0.006 (0.002%)0.064 (0.019%)0.027 (0.008%)339.3781.76×
PreSTO-predictive8295.079 (99.948%)0.003 (0.001%)0.023 (0.008%)0.006 (0.002%)0.085 (0.029%)0.036 (0.012%)295.2322.02×
PreSTO-predictive10273.184 (99.936%)0.004 (0.001%)0.028 (0.010%)0.006 (0.002%)0.096 (0.035%)0.040 (0.015%)273.3582.18×
PreSTO-predictive12267.084 (99.925%)0.005 (0.002%)0.036 (0.013%)0.006 (0.002%)0.109 (0.041%)0.045 (0.017%)267.2852.23×
PreSTO-predictive16247.561 (99.898%)0.007 (0.003%)0.057 (0.023%)0.007 (0.003%)0.130 (0.052%)0.053 (0.021%)247.8152.41×
PreSTO-predictive20239.153 (99.862%)0.010 (0.004%)0.089 (0.037%)0.008 (0.003%)0.159 (0.066%)0.065 (0.027%)239.4842.49×
PreSTO-predictive32216.582 (99.719%)0.020 (0.009%)0.258 (0.119%)0.009 (0.004%)0.228 (0.105%)0.096 (0.044%)217.1922.75×

Conclusion. LLM generation and scoring accounts for at least 99.78%99.78\% of every request for PowerMH and 99.72%99.72\% for EntropyCut. All other components together take at most 0.610.61 s per request (0.22%0.22\% and 0.28%0.28\%), reached at budget 32.

AuthorsOpenReview ↗

Replies to all reviewers (Part 3)

Q3: Fair comparison for MultiTryMH

Reviewer 6Y82: For MultiTryMH, can you provide a comparison using identical completed prompts, identical score-reuse optimizations, and the same timing boundary?

Reviewer 6tGK: The MultiTryMH comparison (2.45x median in the abstract, up to 8.1x) pits full MultiTryMH steps including candidate rescoring against a PreSTO version that skips rescoring, and many rows come from incomplete runs over different prompt sets (e.g. n=17/1), so it does not belong in the abstract.

For a fair comparison, we now follow the released code of the MultiTryMH paper (Guo et al., 2026): we reimplemented its transition rule as the sequential baseline on our vLLM backend, built PreSTO-MultiTryMH on that same implementation, and compare the two on the same prompts, with the same score reuse and timer.

Experiment setting: Qwen3.5-9B on the first 20 LCB V6 prompts, α=4\alpha=4, one 1,024-token block, 2 candidates per transition, one seed. Both methods use the same MultiTryMH implementation, which follows the released code in its candidate weights, selection, and acceptance rule, with every candidate drawn at proposal temperature 1/α=0.251/\alpha=0.25.

Table 3: MultiTryMH and PreSTO-MultiTryMH under matched conditions.

KKPrefetch budgetCompleted promptsTransitions per call: sequential / PreSTOEnd-to-end time (s): sequential / PreSTOSpeedup of PreSTO
102020 of 201.00 / 2.5361.6 / 49.71.24×
103020 of 201.00 / 2.5361.6 / 53.21.16×
104020 of 201.00 / 2.6761.6 / 52.31.18×
105020 of 201.00 / 2.8661.6 / 53.71.15×

Conclusion. Under matched conditions, PreSTO-MultiTryMH is 1.15×1.15\times to 1.24×1.24\times faster than sequential MultiTryMH across budgets, with budget 20 the fastest. Because these runs are computationally expensive, we will update the MultiTryMH results in Table 1 of the paper, for all datasets and base LLMs, in the next revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.