acceptodds
Under review as a conference paper at ICLR 2027

Exact Power Sampling for Language Models with Reusable Exploration

12 views

Abstract

Power sampling sharpens a base model’s sequence distribution at inference time, eliciting reasoning performance comparable to reinforcement learning with verifiable rewards (RLVR) without additional training or external verifiers. However, existing methods largely rely on asymptotic approximations without finite-budget exactness guarantees, leaving efficient exact power sampling a key challenge. Our key insight is that local prefix-tree exploration yields globally valid, progressively tighter bounds on target mass, enabling exact sampling even when exploration is incomplete. Building on this structure, we introduce RSPS, an adaptive rejection sampler that uses sparse prefix refinement to guarantee exactness from the first output sample. We prove that acceptance and rejection feedback provide a stochastic oracle for prefix exploration, and amortize exploration costs across samples by reusing the resulting refinements. Experiments across multiple tasks and models show that, compared with existing methods, RSPS reduces distributional error to the level of finite-sample statistical fluctuations under matched compute budgets and meets stricter sampling-fidelity requirements at lower computational cost.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLMs, reasoning, rejection sampling, inference-time compute

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_ucEAOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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.
  2. 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.
  3. 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.

1 comment

We thank Reviewer ucEA for the thorough review and helpful suggestions, which directly improved the clarity and rigor of our revision.

[Weakness 1 & Question 2] Hyperparameters, FLOP protocol, latency, and memory:

  • Configurations & FLOP Protocol (Section 4 & Appendix F.1–F.2, Table 3): RSPS uses block size L=32L=32, candidate count N=16N=16, and α=2\alpha=2; baselines follow Power-SMC/MH setups with exact particle/step budgets, dataset sizes (198/500/969/500198/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.31s57.31\text{s} on MBPP and 86.67s86.67\text{s} on MATH500—faster than MH (224.21s224.21\text{s} / 153.15s153.15\text{s}) but slower than Power-SMC (54.51s54.51\text{s} / 74.97s74.97\text{s})—while using slightly less peak VRAM than Power-SMC (18.4518.45 vs. 18.66 GiB18.66\text{ GiB} on MBPP; 18.4918.49 vs. 18.69 GiB18.69\text{ GiB} on MATH500).

[Weakness 1 & Question 1] Exact blockwise target, transition algorithm, and exactness scope:

  • Complete Algorithm & Scope (Section 3, Appendix A Eq. 19 & Algorithm 1): At block bb, RSPS connects retained prefixes to a virtual root with weights η^b−1(s)\hat{\eta}_{b-1}(s) and draws NbN_b unweighted trajectories from the exact block target qb(su)∝η^b−1(s)pθ(u∣s)αq_b(su) \propto \hat{\eta}_{b-1}(s)p_\theta(u\mid s)^\alpha, preserving duplicates via empirical frequency η^b(s)\hat{\eta}_b(s) and returning XB1X_B^1 at the final block. Lemma 2 guarantees exactness from the first sample for each fixed block target qbq_b, while cross-block empirical propagation error relative to πα\pi_\alpha is bounded in Appendix D.

[Weakness 2 & Question 3] Section 5 reference model, missing mass, and empirical comparison in Eq. (13):

  • 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)\tilde{p}(v\mid s) strictly over observed tree branches (α=2\alpha=2). Thus p~\tilde{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)=1N∑i=1N1Xi=y<tp_{32}^{\text{RSPS}}(y_{\lt t}) = \frac{1}{N}\sum_{i=1}^N \mathbf{1}\\{X_i = y_{\lt t}\\}; we corrected Eq. (13) and its text accordingly, while Figure 3(c–d) remains unchanged.

Reviewer_WKvNOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

One perspective on reinforcement learning is that it simply sharpens the base model's distribution. This perspective has motivated a number of power sampling-based methods that sample from the temperature-scaled language model distribution instead, directly targeting a sharpened distribution rather than inducing it through reinforcement learning. The key limitation of prior work is that the way they sample from this distribution is heuristic and does not actually target the correct temperature scaled language model distribution. This paper proposes a nice adaptive algorithm based on the simple observation that the marginal distribution of a prefix adaptively provides an upper bound needed for rejection sampling for its descendants. They evaluate this method on several math competition benchmarks, showing that it performs favorably in terms of accuracy and performance against a number of reasonable baseline methods.

Critical strengths

This is quite a nice insight that you can use this simple upper bound within a rejection sampling framework. It's quite natural given an arithmetic coding/prefix tree perspective on autoregressive sampling. It's quite natural. I think this nice technical insight and is a valuable contribution to the power sampling literature and also contributes to developing accurate but tractable sample. There's also some nice engineering insights on how to exploit caching etc...

Critical weaknesses

The experimental evaluation is thin. There's only 3 benchmarks evaluated. I think that in practice the blockwise algorithm introduces approximation error. I think also comparing to an RL baseline would be important to get a sense of whether the temperature scaled policy is actually reasonable.

Questions for authors

How much do the efficiency improvements can be attributed to better expansion of the prefix-tree after failed rejection sampling proposals as opposed to caching across model attempts?

2 comments

We thank Reviewer WKvN for the encouraging feedback. We have added a code generation benchmark (MBPP), a same-backbone RL baseline, blockwise error bounds, and an efficiency attribution ablation.

[Weakness 1] Broader evaluation (MBPP), RL baseline comparison, and blockwise approximation error:

  • New Benchmark — MBPP (Appendix H, Table 7): On the 500-problem MBPP test split (pass@1), RSPS achieves 70.4%70.4\% (22.57×22.57\times FLOPs) on Qwen3.5-9B vs. Power-SMC's 66.2%66.2\% (32.34×32.34\times) and MH's 68.6%68.6\% (26.83×26.83\times), and 72.8%72.8\% (21.94×21.94\times) on gemma-4-12B vs. Power-SMC's 71.8%71.8\% (25.66×25.66\times) and MH's 71.2%71.2\% (27.13×27.13\times).
  • Same-Backbone RL Baseline (Appendix I, Tables 8–9): Due to compute and time constraints on the 9B/12B models, we trained Qwen3.5-2B with GRPO on the MATH training split (7,500 problems, 300 steps). On in-domain MATH500, training-free RSPS achieves 65.2%65.2\% (matching/slightly exceeding RL's 65.0%65.0\% vs. 58.0%58.0\% base). Across out-of-domain benchmarks, single-domain RL degrades below the base model whereas RSPS improves consistently: GPQA Diamond (49.0%49.0\% vs. 24.2%24.2\% RL / 39.9%39.9\% base), MMLU-Pro (50.1%50.1\% vs. 27.0%27.0\% RL / 38.0%38.0\% base), and MBPP (40.0%40.0\% vs. 32.0%32.0\% RL / 35.0%35.0\% base).
  • Blockwise Approximation Error (Appendix D): We added explicit O(N−1)O(N^{-1}) marginal bias and O(N−1/2)O(N^{-1/2}) empirical TV bounds in Appendix D (Theorems 1–2, Proposition 1).

[Question 1] Efficiency attribution (Tree expansion after failed proposals vs. Caching across attempts):

  • Component Ablation (Section 5.2, Table 2 & Appendix G.1, Table 5): Under L=32,α=2,K=16L=32, \alpha=2, K=16, full RSPS requires 319.2319.2 evaluations (−98.4%-98.4\% vs. naive rejection sampling). Disabling rejection-guided tree expansion increases cost 7.04×7.04\times (to 2246.82246.8, as acceptance drops from 29.30%29.30\% to 5.82%5.82\%), whereas disabling cross-attempt caching increases cost 4.07×4.07\times (to 1299.41299.4), and disabling acceptance-path refinement increases cost 1.22×1.22\times (389.4389.4). Thus, rejection-guided prefix expansion contributes the largest efficiency gain in this setting, while caching (75.36%75.36\% hit rate) amortizes forward evaluations across attempts.

I think the authors for their thoughtful response. I've updated my score.

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

This paper proposes an adaptive rejection sampler, RSPS, for power sampling using sparse prefix refinement, with theoretical guarantees of exactness under adaptive refinement. The experiments show that RSPS achieves comparable accuracy for existing power sampling methods with lower computational cost. The authors also provide additional analysis that demonstrates distributional error under certain computational budgets across different power sampling methods.

Critical strengths
  1. The paper proposes a new rejection sampling method and provides a detailed theoretical analysis of exactness under adaptive refinement and rejection feedback, which is meaningful for better understanding power sampling methods.
  2. The experimental results show that RSPS achieves comparable or slightly better performance than MH and SMC power sampling methods with lower FLOPs. The paper also provides additional analysis of TV error and computational cost.
Critical weaknesses
  1. The main contribution of this paper is exact power sampling, while the experiments use blockwise sampling. This is reasonable in practice, but the paper provides limited quantitative analysis of the approximation error introduced by the blockwise setting, for example, how it depends on the block length and the number of candidates.
  2. The theoretical analysis does not sufficiently discuss its implications for computational efficiency. It is unclear under what conditions RSPS could achieve lower computational cost than SMC and MH methods, and which part of RSPS contributes most to the observed FLOPs reduction.
Questions for authors
  1. Could the authors provide a more detailed error analysis for blockwise sampling, such as an upper bound on the approximation error under some assumptions?
  2. Could the authors provide some ablation studies on the blockwise setting, such as varying the block size? A computational cost ablation study of the main components would help clarify where the FLOPs improvements come from in practice
3 comments

We thank Reviewer Ngyc for the constructive feedback. We have revised the paper to add quantitative blockwise error bounds, block-size sensitivity sweeps, and component-wise cost ablations.

[Weakness 1 & Question 1] Quantitative error analysis for blockwise sampling:

  • Blockwise Approximation Error Bounds (Section 3 & Appendix D): We derive explicit TV bounds in Appendix D in terms of block length LL, block count B=⌈T/L⌉B=\lceil T/L \rceil, and candidate count NbN_b:
    • Single-sample marginal bias (Theorem 1, Eq. 40): Under continuation mass variation ratio Mb/mb≤κbM_b/m_b \le \kappa_b, TV(PN,πα)≤∑b=1B−1κb−1Nb\mathrm{TV}(P_N, \pi_\alpha) \le \sum_{b=1}^{B-1} \frac{\kappa_b - 1}{N_b}. For uniform Nb=NN_b=N and κb≤κ\kappa_b \le \kappa, this yields (⌈T/L⌉−1)(κ−1)N=O(N−1)\frac{(\lceil T/L \rceil - 1)(\kappa - 1)}{N} = O(N^{-1}), decreasing with fewer block boundaries under a common κ\kappa bound.
    • Single-run empirical TV & horizon mismatch (Proposition 1 & Appendix D.4, Eqs. 43–45): Empirical histogram TV scales as O(N−1/2)O(N^{-1/2}), while intermediate block-boundary truncation bias is separately bounded by bL≤tanh⁡(14log⁡Mm)b_L \le \tanh(\frac{1}{4}\log\frac{M}{m}).

[Weakness 2 & Question 2] Conditions for efficiency gains, block-size ablations, and component-wise FLOPs attribution:

  • When RSPS Outperforms SMC & Block-Size Ablation (Section 5.3 & Appendix G.2, Table 6): Sweeping block length L∈{16,18,…,32}L \in \{16,18,\dots,32\} and candidate count N∈{1,2,4,16,32,64,128,256}N \in \{1,2,4,16,32,64,128,256\} shows that at very small budgets, RSPS incurs cold-start envelope-tightening overhead. However, across all 9 block lengths, once expansions exceed a crossover threshold C×(L)C_\times(L) (Table 6, rising overall from 23.823.8 at L=16L=16 to 134.9134.9 at L=32L=32, Pearson r=0.805r=0.805), RSPS achieves lower interpolated TV at matched cost within the observed budget range because exact block samples require far fewer trajectories than SMC (e.g., ∼32\sim 32 vs. ∼256\sim 256 at L=32L=32 for TV ≈0.35\approx 0.35). At fixed N=16N=16, RSPS beats SMC in mean TV across all 9 block lengths, while larger LL generally shifts C×(L)C_\times(L) higher.
  • Component-Wise Cost Ablation (Section 5.2, Table 2 & Appendix G.1, Table 5): Under L=32,α=2,K=16L=32, \alpha=2, K=16, full RSPS requires 319.2319.2 distribution evaluations (−98.4%-98.4\% vs. naive rejection sampling's 19768.819768.8). Removing rejection-path refinement increases cost 7.04×7.04\times (2246.82246.8, acceptance drops from 29.30%29.30\% to 5.82%5.82\%), removing cross-attempt caching increases cost 4.07×4.07\times (1299.41299.4), and removing acceptance-path refinement increases cost 1.22×1.22\times (389.4389.4). Thus, rejection-guided refinement is the primary driver, aided by caching.

Thanks for the detailed response and additional experiments. The new error bounds and component ablations address several of my original concerns and help clarify the sources of computational savings. However, despite the lower estimated FLOPs, the reported wall-clock latency does not show an improvement over Power-SMC. It would be helpful to further clarify this discrepancy. The responses have improved the paper, but I still have some concerns about the overall strength of the contribution, and I will reconsider my score after discussing the paper with the other reviewers.

Thank you for your thoughtful follow-up and for considering our additional analysis and experiments. We appreciate the opportunity to clarify the difference between FLOPs and wall-clock latency.

Power-SMC works much like batched decoding, which is GPU-friendly. RSPS uses rejection sampling to sample exactly from each specified block target, but stopping and restarting attempts can add scheduling overhead and reduce GPU efficiency.

We view RSPS as representing a different family of sampling methods, with its own strengths rather than improvements on every metric. Power-SMC’s GPU-friendly design has a latency advantage, and our results demonstrate a practical trade-off: for example on MBPP, RSPS improves pass@1 by 4.2 percentage points and reduces estimated FLOPs by about 30%, while being only 5.1% higher latency。

Beyond these results, our contribution lies in a different way to formulate and structure the power-sampling problem. This opens another direction for algorithm design, and we hope this perspective can also offer useful insights for future sampler design. RSPS also improves on MH across all the reported performance metrics.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.