- 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
-
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.
-
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.
-
The paper is well written and organized. The figures clearly illustrate the method, and the tables summarize the experimental results effectively.
Critical weaknesses
- 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
-
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?
-
Could you report end-to-end speedups, including the overhead of subtree construction, predictor inference, dynamic programming, etc.?
-
Could you clarify how acceptance probabilities are computed for prefetched descendants? After accepting , the next proposal should use , but the inspected public code snapshot appears to use . How does the implementation account for the actual current state?
2 comments
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, , 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.
| Method | Prefetch budget | Generation and scoring | Prediction | Dynamic Programming compute | Subtree management | Traversal and state updates | Other overhead | Total |
|---|---|---|---|---|---|---|---|---|
| Sequential PowerMH | — | 566.578 (99.980%) | — | — | — | 0.053 (0.009%) | 0.058 (0.010%) | 566.689 |
| PreSTO-BFS | 4 | 515.169 (99.973%) | — | — | 0.011 (0.002%) | 0.080 (0.016%) | 0.046 (0.009%) | 515.306 |
| PreSTO-BFS | 8 | 461.296 (99.960%) | — | — | 0.010 (0.002%) | 0.114 (0.025%) | 0.062 (0.013%) | 461.482 |
| PreSTO-BFS | 10 | 432.863 (99.951%) | — | — | 0.010 (0.002%) | 0.132 (0.030%) | 0.072 (0.017%) | 433.077 |
| PreSTO-BFS | 12 | 416.837 (99.940%) | — | — | 0.011 (0.003%) | 0.156 (0.037%) | 0.084 (0.020%) | 417.087 |
| PreSTO-BFS | 16 | 386.436 (99.921%) | — | — | 0.012 (0.003%) | 0.192 (0.050%) | 0.102 (0.026%) | 386.741 |
| PreSTO-BFS | 20 | 365.518 (99.905%) | — | — | 0.012 (0.003%) | 0.222 (0.061%) | 0.112 (0.031%) | 365.864 |
| PreSTO-BFS | 32 | 330.404 (99.845%) | — | — | 0.016 (0.005%) | 0.324 (0.098%) | 0.172 (0.052%) | 330.916 |
| PreSTO-predictive | 4 | 378.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-predictive | 8 | 332.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-predictive | 10 | 321.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-predictive | 12 | 303.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-predictive | 16 | 293.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-predictive | 20 | 276.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-predictive | 32 | 268.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 of every request, for PowerMH and for PreSTO under both traversal rules. All other components together take at most of the total time.
Q3: Acceptance against the actual current state
Could you clarify how acceptance probabilities are computed for prefetched descendants? After accepting , the next proposal should use , but the inspected public code snapshot appears to use . 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 , the next proposal is evaluated with .
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
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, proposal temperature 0.25, K=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.
Conclusion: With EOS stopping enabled, our method still accelerates the baseline, by 2.00× at budget 10 and 2.24× at budget 20.