- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes RSPS, an adaptive rejection sampler for the sequence-level power distribution of a language model. Prefix probabilities provide upper bounds on unexplored subtree mass; sparse frontier refinement tightens the envelope, while cached model evaluations can be reused across samples. The paper proves exactness of accepted samples under history-dependent refinement and characterizes acceptance and rejection feedback as signals for useful exploration. For long outputs, the practical method uses finite blocks and candidate prefixes: exactness applies to each current block target, while horizon and candidate-set approximations remain. Experiments report reasoning accuracy and relative FLOPs for two models on three datasets, together with fixed-prompt sampling diagnostics.
Critical strengths
-
The sampler has a clean fixed-target correctness argument. The prefix envelope, local power proposal, and rejection correction cancel to give the desired unnormalized sequence probability. Appendix C correctly conditions on the adaptive history, and Appendix A specifies a frozen envelope within each parallel batch and return order by attempt index. These details are important for preserving the first-returned-sample guarantee despite adaptive refinement and parallel completion.
-
Reusing exploration is a plausible and potentially useful efficiency mechanism. Sparse token groups avoid explicitly instantiating every vocabulary branch, and accepted and rejected attempts both contribute cached model evaluations. The feedback identities explain why rejected regions contain removable envelope mass. The reported task results show equal or better accuracy with fewer FLOPs than Power-SMC in all six configurations, making a fully documented evaluation of the approach worthwhile.
Critical weaknesses
-
The precise target and configuration of the practical sampler are not sufficiently specified to assess the main efficiency claim. The paper correctly acknowledges that blockwise sampling retains finite-horizon and candidate-set error, but does not provide a complete block-transition algorithm, including prefix weights, duplicate handling, pruning, and final output selection. Important experimental settings are also missing: the numerical power exponent, block horizon, sample/particle and batch counts, MH budget, dataset subset sizes and selection, and the FLOP accounting protocol. Section 5.1 refers to the power exponent from Section 4, but Section 4 does not give its value. Without these details, Table 1 cannot establish a reproducible or clearly matched trade-off, and the headline guarantee must be understood as exactness for a specified fixed target with potentially unbounded computation, not finite-budget exact full-sequence generation by the deployed blockwise method.
-
The sampling-fidelity diagnostics do not establish the claimed level of distributional accuracy. Section 5.1 constructs a non-exhaustive reference from 120,000 responses for one prompt, but does not quantify missing target mass or justify the assertion that reference error is small. Matching the mean of sequence power mass is only a single-moment check. In Section 5.3, Equation 13 evaluates RSPS as a distribution obtained by deduplicating retained trajectories and renormalizing their power masses, while SMC is evaluated using its particle weights. The former is not the empirical distribution of the exact returned samples; it evaluates a different candidate-set representation. The paper should distinguish these objects, justify this comparison, and account for samples or target mass outside the reference support before interpreting the resulting TV curves as general sampling-fidelity evidence.
Questions for authors
- Algorithm clarification: What is the exact blockwise target at every boundary, and how are candidate prefixes, weights, duplicates, and discarded regions carried forward? Please give the complete transition and final selection procedure, and specify precisely which returned distributions inherit the exactness theorem.
- Reproducibility clarification: Please provide the missing exponents, horizons, particle/sample counts, baseline budgets, dataset subsets, and FLOP methodology. Under matched conditions, what are the time-to-first-sample, total latency, and cache-memory costs? FLOP savings alone do not establish practical speedups.
- Fidelity clarification: How is the 120,000-response reference generated, what is its missing-mass error, and how is support outside the reference handled? Can the exact-sample claim be checked against enumerable ground truth, with empirical-sample fidelity separated from the deduplicated candidate-set comparison in Equation 13?
These questions concern the algorithm and evidence already used to support the paper's principal claims.
We thank Reviewer ucEA for the thorough review and helpful suggestions, which directly improved the clarity and rigor of our revision.
Configurations & FLOP Protocol (Section 4 & Appendix F.1–F.2, Table 3): RSPS uses block size L=32, candidate count N=16, and α=2; baselines follow Power-SMC/MH setups with exact particle/step budgets, dataset sizes (198/500/969/500), and analytical FLOP formulas documented in Table 3 & Appendix F.2. Table 1 has been corrected to include all evaluation problems, counting overlength failures as incorrect.
Wall-Clock Latency & Peak Memory (Appendix F.3, Table 4): On a single A6000 GPU (Qwen3.5-9B, batch 1, returning 1 sequence so TTFS equals total latency), RSPS takes 57.31s on MBPP and 86.67s on MATH500—faster than MH (224.21s / 153.15s) but slower than Power-SMC (54.51s / 74.97s)—while using slightly less peak VRAM than Power-SMC (18.45 vs. 18.66 GiB on MBPP; 18.49 vs. 18.69 GiB on MATH500).
Closed Finite-Support Reference Model (Section 5 & Appendix E, Eq. 46): Rather than treating 120k rollouts as an approximation of the original LLM, we deduplicated them into a closed prefix tree and renormalized p~(v∣s) strictly over observed tree branches (α=2). Thus p~ is a closed, enumerable finite-support autoregressive model with zero missing mass and no out-of-support trajectories within this finite model.
Eq. (13) Correction (Section 5.3 & Figure 3): Thank you for catching the misstatement in Eq. (13). Our experiments already evaluated RSPS using its unweighted empirical distribution p32RSPS(y<t)=N1∑i=1N1Xi=y<t; we corrected Eq. (13) and its text accordingly, while Figure 3(c–d) remains unchanged.