acceptodds
Under review as a conference paper at ICLR 2027

Exact Probability Powering from Samples Alone at the Collision Scale

Abstract

Temperature sampling normally needs the probability distribution, yet many systems, from simulators to language models reasoning toward a final answer, provide only *samples*. We ask how to sample exactly at temperature from samples alone, drawing each outcome with probability proportional to , the th power of its probability, for a fixed integer (probability powering). Known approaches face a trade-off between speed and exactness. Classical rejection sampling, which keeps an outcome only when fresh samples agree, is exact but slow: with equally likely outcomes, it needs samples. The first-collision shortcut, which returns the first outcome to appear times among all samples drawn so far (a -fold collision), is fast—needing only samples—but biased. Refined collision-based methods reduce this bias but remain approximate. In this work, we show that this trade-off is unnecessary. We define the *collision map*, a random update built from one collision and the other outcomes seen before it, and prove that it preserves the target distribution. Our sampler, **Collision-map CFTP**, composes these maps backward in time (coupling from the past) *without knowing* the probabilities or which outcomes are possible. It returns an *exact* output after a bounded expected number of collisions, needing only samples instead of rejection's . Conversely, every sampler that is exact for every distribution must see its output times before returning it, so none can beat this method on *any* input by more than a factor depending only on (instance optimality). *Exactness thus costs only a constant factor over the biased shortcut*, e.g., for squaring, we prove that this factor is below on every input and tends to on large uniform inputs. Simulations match the predicted costs and output distributions. At temperature over a million equally likely outcomes, our Collision-map CFTP uses about 3,400 samples per output on average, whereas rejection needs about 2,100,000. All theorems are formally verified in Lean 4.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
exact sampling, probability powering, power sampling, coupling from the past, Bernoulli factories, sample complexity, perfect simulation

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_d2EWOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

Given access only to an oracle that generates label ii with probability pip_i the paper considers how to draw samples with probability proportional to pikp_i^k (for kk an integer ≥2\ge 2). The paper also shows that the expected cost of the method (in terms of number of oracle-calls) is within a kk-dependent scaling factor of the best achievable expected cost. Through use of a carefully constructed data-structur the method can be applied when the support of pp is unknown a-priori and/or when it is countably infinite.

Critical strengths

The paper provides a clever solution to this exact sampling problem. Notable advances include :

  • use of an innovative data-structure that enables implementation of a Markov-chain CFTP (coupling from the past) technique to obtain exact samples even when the support of pp is unknown and/or countably infinite
  • substantial and thorough supporting analysis, for example to prove that the expected number of oracle calls needed per sample is optimal to within a kk-dependent scaling factor of best-achievable.
Critical weaknesses

An expanded discussion about potential uses of the method would help promote the significance of the work.

The paper would be strengthened by a more detailed empirical evaluation of a range of representative non-uniform sampling cases, covering for example the impact of kk on costs, and quantified in terms of both number of oracle calls and wall clock timings

Questions for authors

(1) Can you expand on the discussion about potential uses of the method, including those that may be of particular interest to an ICLR audience.

(2) The theoretical results establish optimality up to a kk-dependent (upper-bounded) factor, but it is less clear how large this factor actually is in practical applications. If time permits could you include an empirical analysis, covering representative non-uniform sampling case(s), to help clarify the range of k for which the method is practically useful/competitive.

(3) It would also be helpful to see some results on the empirical ratio between the method’s sample cost (measured in number of oracle-calls) and the first-collision lower bound for representative distribution(s) and several values of kk, and compare it with the theoretical upper bound.

Some corrections that I spotted: The first listed main contribution says the algorithm 'returns exactly qkq_k on any countable support' whereas it actually returns samples under distribution qkq_k. Similar statements appear elsewhere, for example in the second paragraph of section 2 and in Theorem 1.

(note: My marking of 2 under soundness reflects the difficulty of validating all of the proofs within the review-time available. To the extent that I have been able to check, I have not identified problems)

6 comments
AuthorsOpenReview ↗

Response to Reviewer d2EW (1/2): the main use for an ICLR audience is demonstrated on LLM reasoning; the k-factor is small in practice (median 1.1–13 for k ≤ 5)

We thank the reviewer for the positive assessment ("a clever solution", "an innovative data-structure", "substantial and thorough supporting analysis") and for the concrete suggestions. Line numbers refer to the revised PDF.

1. Uses for an ICLR audience: exact sharpening of LLM answers, now demonstrated (W1, Q1)

(W1) An expanded discussion about potential uses of the method would help promote the significance of the work.
(Q1) ... including those that may be of particular interest to an ICLR audience.

Sharpening LLM answers is a current route to better reasoning, and we ran our sampler in the same experiment as prior work (L461–464):

  • Power sampling (Karan & Du, ICLR 2026) samples p4p^4 of whole generations on MATH500 with Qwen2.5 models and nearly matches RL post-training.
  • Marginal sharpening (Arzhantsev et al., 2026) targets exactly our q4q_4 on MATH-500 answers, and is more accurate than standard sampling (0.90 vs 0.81 for Qwen3-1.7B).

Both need token probabilities and are approximate. Even with token probabilities, an answer's probability is a sum over all reasoning paths that reach it (L43–45). Our sampler needs only independent generations: one oracle call is one LLM generation, and a label is its final answer. In the same setting (MATH500, Qwen2.5, k=4), it needs 16–384× fewer oracle calls than exact rejection:

Oracle calls (LLM generations) per exact output, k=4OursExact rejection
Qwen2.5-7B, MATH50028436
Qwen2.5-7B, AIME 2024/2519014,666
Qwen2.5-1.5B, MATH50011142,476

Rejection here is the stronger early-abort variant (L64–65). The General Response describes the setup. The method applies wherever only samples are available; every use below is stated in our paper. As you suggest (W1), the revision expands the discussion of uses in Sec. 8 (L523–527):

Language models and other generators

  1. Diffusion language models such as LLaDA-8B give likelihoods only through variational bounds or Monte Carlo estimates (L1485–1488); ours needs only their samples.
  2. Exact references for approximate sharpening (L57–59, L523–527). Exact samples keep Monte Carlo averages under qkq_k unbiased and measure the bias of approximate samplers: CALM's batch method has total-variation bias 0.038 at 16 generations per output on the same MATH500 answers (7B).
  3. Sharpened targets for distillation when a teacher exposes only its outputs (L523–524).
  4. Likelihood-free generators such as CALM's continuous autoregressive models: a drop-in replacement for the rejection stage of CALM's exact temperature sampler (L1480), for every real power ≥ 2 (L531–533).

Beyond language models 5. Simulators and probabilistic programs: powering the law of a discrete output of a random execution, whose probability sums over executions (L43–45, L1460–1464). 6. Marginal MAP estimation by powering an intractable marginal posterior (Doucet et al., 2002; L1465–1466).

2. The median factor is 1.1–13 for k ≤ 5, far below the proven bound (Q2, Q3)

(Q2) ... it is less clear how large this factor actually is in practical applications ...
(Q3) ... the empirical ratio between the method's sample cost ... and the first-collision lower bound for representative distribution(s) and several values of kk, and compare it with the theoretical upper bound.

Small: for k ≤ 5 the median factor is 1.1–1.3 on MATH500 answers (Qwen2.5-7B), 2.9–13 on its AIME answers and 2.3–8.0 on non-uniform synthetic distributions, against a proven bound of up to 1.3e9.

By Eq. 6 the ratio in Q3 is exactly E[T]=E[N]/μk\mathbb E[T]=\mathbb E[N]/\mu_k. We measured it on real LLM answer distributions and on 24 non-uniform synthetic distributions (Zipf, heavy-head, dyadic, answer-like, countably infinite geometric):

k2345
Qwen2.5-7B answers, MATH500 (median problem)1.121.181.241.30
Qwen2.5-1.5B answers, MATH500 (median problem)2.212.953.784.80
Qwen2.5-7B answers, AIME 2024/25 (median problem)2.895.448.6113.5
Synthetic distributions (median)2.333.605.448.03
Theoretical upper bound CkC_k10.84.2e45.5e61.3e9

Log-linear fits give a growth of ×1.05, ×1.29, ×1.66 and ×1.51 per unit increase of k for the four rows. We agree that the proven CkC_k grows quickly with k, and the paper says so (L1125–1126). The measured factor stays far below it: over all 39 synthetic distributions, its largest value for k ≤ 5 is 32.9.

The revision adds this study as App. E (L1512–1571): all 39 distributions, k up to 8, the largest values (Table 2, L1540–1553) and the comparison with rejection (L1564–1568).

AuthorsOpenReview ↗

Response to Reviewer d2EW (2/2): competitive at every tested k unless the support is tiny; negligible overhead; public Lean code; wording corrected

3. Competitive at every tested k unless the support is tiny (Q2)

(Q2) ... to help clarify the range of k for which the method is practically useful/competitive.

At every k we tested, our sampler is cheaper than exact rejection unless the distribution has at most five effective labels, and its advantage grows with k.

  • On real answer distributions the saving is 1.2×, 3.3×, 16×, 95× at k=2–5 (Qwen2.5-7B, MATH500) and 2.2×, 18×, 384×, 12,000× (1.5B); per-k costs are in Part 1 of our reply to ipiH.
  • Rejection is cheaper only when the effective support is tiny: in our study, only on distributions with at most 5 effective labels (1/∑ipi2≤51/\sum_ip_i^2\le5), such as a fair coin or one label with 80% of the mass. For k ≤ 5 we then pay at most 2.6× (fair coin, k=5: 119 vs 46 samples), and at most 4.3× for k ≤ 8 (App. E).
  • No need to know in advance which method is cheaper. For practical use, a simple exact hybrid picks our sampler or rejection for each output using only the samples of earlier outputs, so every output stays exact and independent. On 1,060 LLM answer distributions it costs on average only about 1% more than the cheaper method.

4. Wall-clock: negligible overhead, and up to 4.3× faster end to end (W2)

... quantified in terms of both number of oracle calls and wall clock timings

  • The sampler's overhead is negligible: about 0.1 µs per oracle call in our compiled implementation (median over the 223 synthetic combinations of distribution and power), and at most 0.5 ms per output in the LLM runs (median 16 µs).
  • End to end, up to 4.3× faster, with live LLM generation on a GPU (k=4; both methods read the same stream of generations; problems chosen in advance to cover diffuse, intermediate and concentrated answers). For Qwen2.5-1.5B on 50 MATH500 problems, half of the problems have their first exact output within 24 s with our sampler and within 56 s with rejection (49/50 vs 32/50 finished within the 300 s limit; mean per-problem speed-up 3.0× [2.1, 4.2]). On the 30 problems with diffuse answers, 29 vs 12 finished, so rejection's median exceeds 300 s, against 57 s for ours (4.3×). For Qwen2.5-7B on 40 MATH500/AIME problems the speed-up is 1.9× [1.4, 2.5]. Unfinished runs count as taking the whole time limit (each run had a time cap); since rejection fails to finish far more often, without the cap the speed-ups would likely be even higher.

5. The proofs can now be checked: public Lean code and large-scale exactness tests

(note: My marking of 2 under soundness reflects the difficulty of validating all of the proofs within the review-time available ...)

We understand, and we have made checking easier:

  • Lean 4 code, now linked in the paper (L556–557): https://anonymous.4open.science/r/exact-probability-powering-45BE. Its lean/README.md maps every named result of the paper to its Lean declarations. We rebuilt it from source at the time of this writing: AXIOM_AUDIT_OK modules=299 declarations=4793 theorems=4089, with no sorry and only three standard axioms: propext, Quot.sound and Classical.choice.
  • Large-scale exactness tests: we drew 1 million outputs in each of 16 settings (k=2–5 on four distributions, one countably infinite). They are consistent with qkq_k and independence: none of the 48 tests rejects after Holm correction. The same tests detect the bias of the first-collision shortcut in all 12 non-uniform settings.

6. Wording corrected to "an exact sample from qkq_k"

The first listed main contribution says the algorithm 'returns exactly qkq_k on any countable support' whereas it actually returns samples under distribution qkq_k. Similar statements appear elsewhere ...

Thank you, and this was our oversight. Saying that a sampler "returns" its target distribution is a common shorthand in the exact-sampling literature, but we should have kept in mind that ICLR has a broader readership. We now write "returns an exact sample from qkq_k" in the contributions (L100), in Sec. 2 (L144) and in Theorem 1 (L156).


We hope these additions address your remaining concerns, and we would be grateful if you would consider raising your score. If any additional result could further improve your assessment of the paper, please let us know, and we will be happy to provide it.

Thank you for your considered responses which have answered my questions in detail. I maintain my rating score at 3 and will increase my soundness score to 3.

In both the joint response and the per-reviewer responses you have provided a lot of information, including detailed evidence/information on the practicality and performance benefits of your method. At this stage you have not added much of this material to the paper. I think it might prove helpful to reviewers still considering their assessments if you could say more about which, if any, of these results you intend to include in the paper, bearing in mind that you now have an additional page of space in the main text.

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

The paper asks how to sample exactly from q_k(i)=p_i^k/Σ_j p_j^k using only IID samples from an unknown discrete distribution, for a fixed integer k≥2 and possibly unknown countable support. A collision block records samples through the first k-fold repetition. Its winner and other observed labels define a random map preserving q_k. Backward composition with a finite default-and-exception representation yields Collision-map CFTP. The expected sample count is at most C_k E[J_k], where J_k is the first collision time. Every universal exact sampler must observe its output k times, giving an instance-wise matching lower bound. For squaring C_2<11, while the uniform-input overhead approaches 8/3.

Critical strengths
  1. The paper establishes matching upper and lower bounds, achieving instance-optimal sample complexity up to a constant factor.
  2. The proposed Collision-map CFTP combines collision-based sampling with CFTP to achieve exact sampling without knowing the probabilities or support, even for countably infinite state spaces.
  3. Experiments confirm the theoretical efficiency gains and sampling correctness, while Lean 4 formal verification further supports the theoretical results.
Critical weaknesses
  • Though proofs are given in the appendix, it is not easy to check their correctness or understand the main idea behind them. The authors mentioned they used Lean to formally check the proofs, but no Lean files are provided.
  • Numerical validation is narrow relative to the available distributional theory. Section 6.1 tests only k=2, with 256 outputs per uniform support size and 20,000 outputs for one four-label distribution. These checks support the predicted asymptotic coefficient and one nonuniform output law, but do not reveal finite-size behavior for skewed or long-tailed distributions or for k≥3.
Questions for authors
  1. How might the practical implications of the instance-optimality guarantee be further clarified under the sample-only oracle and universal exactness assumptions, especially in light of the rapidly growing constants for larger k?
  2. When Dice Enterprise is specialized to the same integer-power transform on a finite alphabet, which part of its construction obstructs an alphabet-independent collision-scale guarantee?
5 comments
AuthorsOpenReview ↗

Response to Reviewer 1dH4 (1/2): the guarantee pays off on LLM reasoning; the measured constants are small; broader numerics

We thank the reviewer for the careful reading and for noting the "matching upper and lower bounds" and the extension to "countably infinite state spaces". We answer your Q1 on practical implications first, then every other point (line numbers refer to the revised PDF):

Your concernShort answer
Practical implications of instance optimality (Q1)a direct use: exact sharpening of LLM answers, with 16–384× fewer generations than exact rejection
Rapidly growing constants (Q1)the proven CkC_k is a worst-case bound; the measured median factor is small: 1.1–1.3 on MATH500 answers (7B) and 2.3–8.0 on 24 non-uniform distributions, k ≤ 5
Narrow numerics (W2)39 distributions (skewed, long-tailed, countably infinite) and k=2–8, now in App. E; 16 million outputs tested for exactness
No Lean files; main idea (W1)code now public; a three-step outline (Part 2)
Dice Enterprise (Q2)its ladder, update and guarantee all grow with the number of possible outcomes (Part 2)

1. The guarantee applies directly to LLM reasoning, and its price there is small (Q1)

(Q1) How might the practical implications of the instance-optimality guarantee be further clarified under the sample-only oracle and universal exactness assumptions, especially in light of the rapidly growing constants for larger k?

  1. The main use is now demonstrated. Run unchanged on LLM reasoning (MATH500 and AIME, Qwen2.5 models; General Response), our sampler draws exact samples of the sharpened answer distribution with 16–384× fewer LLM generations than exact rejection at k=4.
  2. Both assumptions hold for LLM answers. Final answers are free-form strings with unknown support, and their probabilities are sums over reasoning paths (L44). A method that is exact only under a promise (known possible outcomes, a parametric family) is not exact there. Promises change the comparison class: "a sampler promised a uniform input could return its first sample, because powering leaves a uniform distribution unchanged" (L179–180; also L1490–1491).
  3. Instance optimality makes the price of exactness explicit. By Thm 2, which holds pathwise, no universal exact method stops before some label has appeared k times. So the only price of exactness is E[T]=E[N]/μk\mathbb E[T]=\mathbb E[N]/\mu_k (Eq. 6): 1.12, 1.18, 1.24, 1.30 at k=2–5 on the median MATH500 problem (Qwen2.5-7B). The sampler needs no tuning, and its cost tracks each input's answer diversity 1/∥p∥k1/\Vert p\Vert_k.
  4. We agree that the proven constants grow rapidly, and the paper says so (L1125–1126). The proven CkC_k (10.8, 4.2e4, 5.5e6, 1.3e9 for k=2–5) comes from a worst-case coupling argument; the measured median factor is 1.1–13. Growth in k is not specific to our construction: on a fair coin, even the gambler's-ruin walk, which knows the two possible outcomes, pays k2/μkk^2/\mu_k = 1.6, 2.2, 2.8, 3.3 for k=2–5, and on the 1.5B model's MATH500 answers exact rejection's factor grows faster than ours (×1.91 vs ×1.29 per unit of k). The theory does not rest on CkC_k: for each fixed k, Thms 1–2 determine the dependence on the input up to a factor independent of pp. This is the standard form of such results: Rényi-entropy estimation at the same collision scale is Θ(n1−1/k)\Theta(n^{1-1/k}) with k-dependent constants (Acharya et al., IEEE TIT 2017), and the instance-optimal threshold algorithm of Fagin, Lotem & Naor (Gödel Prize 2014) is optimal up to a ratio that grows with the number of input lists. We leave the optimal k-dependence open (L530–531, L1377).

2. Broader numerics: 39 distributions and k up to 8 in a new appendix, with an exact output law (W2)

... do not reveal finite-size behavior for skewed or long-tailed distributions or for k≥3.

The revision adds exactly these cases as App. E (L1512–1571): 39 skewed, long-tailed, countably infinite and uniform distributions, with k up to 8 (223 combinations, 200–10,000 outputs each). Cost over the lower bound, E[N]/μk\mathbb E[N]/\mu_k, median over each family (App. E also gives the other families and the largest values):

k=2k=3k=4k=5
Zipf, exponent 0.5–2 (8 distributions)2.573.835.457.55
Heavy head: one label with 50–95% mass, long uniform tail (6)1.371.491.581.67
Answer-like: one or two frequent labels, Zipf tail (3)2.343.605.297.86
Uniform, n=220n=2^{20}2.663.995.577.95
Uniform limit, n→∞n\to\infty (Prop. 13)2.673.915.006.00

The output law is exact on such inputs too. We drew 1 million outputs in each of 16 settings: k=2–5 on four distributions (uniform, Zipf, the paper's four-label law, countably infinite geometric). The outputs are consistent with qkq_k and independence: none of the 48 tests (fit to qkq_k and two pairwise independence tests per setting) rejects after Holm correction. The same tests detect the bias of the first-collision shortcut in all 12 non-uniform settings.

AuthorsOpenReview ↗

Response to Reviewer 1dH4 (2/2): the Lean files are public and rebuild cleanly; Dice Enterprise's construction grows with the number of possible outcomes

3. The Lean files are public, and the main idea fits in three steps (W1)

Though proofs are given in the appendix, it is not easy to check their correctness or understand the main idea behind them. The authors mentioned they used Lean to formally check the proofs, but no Lean files are provided.

The Lean files are public. The submission offered them on request; they are now linked in the reproducibility statement (L556–557): https://anonymous.4open.science/r/exact-probability-powering-45BE (Lean 4.27.0, pinned Mathlib).

  • lean/README.md lists every named result of the paper (e.g., Theorem 1, Exact sampling with cost at the collision scale) with its Lean declarations; STATEMENT_MAP.csv covers all 367 declarations, including the unnumbered calculations, and MainTheorems.lean checks each of them.
  • We rebuilt the package from source at the time of this writing: AXIOM_AUDIT_OK modules=299 declarations=4793 theorems=4089 entries=367. The axiom audit reports only propext, Quot.sound and Classical.choice.
  • Theorem 1, abridged from lean/ProbabilityPowering/PowerFactory.lean:
theorem powerFactory_general (p : PMF α) (hk : 2 ≤ k) :
    0 < coalescenceConstant k ∧
    (∀ᵐ ω ∂iidStream p, oracleCallTime k ω ≠ ⊤) ∧
    (∀ y, iidStream p {ω | oracleOutput k _ ω = y} = p y ^ k / powerSum p k) ∧
    meanOracleCost p k = meanCollisionTime p k * (∫⁻ ω, cftpTime … ∂iidStream p).toReal ∧
    meanOracleCost p k ≤ coalescenceConstant k * meanCollisionTime p k ∧ ...

Theorem 2 fixes the algorithm and its seed law and then quantifies over every source PMF (UniversallyExact); universallyExact_callTime_ae_ge_collision proves collisionTime ≤ callTime almost surely on the same stream. CORRESPONDENCE.md explains these quantifiers.

The main idea fits in three steps, outlined in the main text (L86–95):

  1. Reversibility by renaming (Sec. 4.2, L243–250). A history that sends x to y never contains x. Renaming y as x gives a history that sends y to x and swaps pykp_y^k for pxkp_x^k, so detailed balance holds without enumerating any state space.
  2. Finite representation (Sec. 4.3, L278–294). The backward composition is a default value plus exceptions at observed labels, so an empty dictionary certifies coalescence on an unknown countable space.
  3. Support-free coalescence (Sec. 5.2, L333–353). After k blocks, every output other than the last k−1 winners lies in all k seen sets. Independence bounds the expected intersection by μkkSk≤kk\mu_k^kS_k\le k^k, the same power sum that sets the block length. Each later block merges any pair with probability at least δk\delta_k.

4. Dice Enterprise's ladder, update and guarantee all grow with the number of possible outcomes (Q2)

(Q2) When Dice Enterprise is specialized to the same integer-power transform on a finite alphabet, which part of its construction obstructs an alphabet-independent collision-scale guarantee?

Three parts of Morina et al. (2022), each tied to the number n of possible outcomes (now in App. C.1, L1395–1422):

  1. The ladder grows with n. pik/∑jpjkp_i^k/\sum_jp_j^k starts as n monomials keike_i at pairwise L1L_1 distance 2k, so the ladder is not connected (their Def. 2.2). Connecting it needs degree at least 2k−1, and augmenting it k−1 times, as DE's R package does, gives n(n+k−2k−1)n\binom{n+k-2}{k-1} states (n2n^2 for k=2; 1.7×1071.7\times10^7 for n=100, k=4).
  2. The update advances one roll at a time. Each step moves to a neighboring monomial (Props. 3.4, 3.6). With more than two faces this update is "not necessarily monotonic" (Sec. 3.3), so CFTP must follow every ladder state. A k-fold repeat is thus built roll by roll: the chain cannot use a repeat that occurred several rolls earlier, and that is where the birthday-scale saving comes from.
  3. The only general guarantee depends on n. Prop. 3.10 bounds the cost by the waiting time for 2d consecutive rolls of one face on a degree-d ladder. With d ≥ 2k−1 this is at least n4k−2−1n^{4k-2}-1 on a fair n-sided die. It is an upper bound on DE's cost, not a lower bound.

Our replacements are, respectively, a dictionary of observed labels, a whole collision block per step, and the k-block intersection bound (Lemma 3), which does not involve n. Measured with DE's own package (best of up to three ladders), DE's cost grows like n0.87n^{0.87} (k=2) and n1.66n^{1.66} (k=3) over n ≤ 12, versus n1/2n^{1/2} and n2/3n^{2/3} for ours; DE costs more than ours in 31 of 32 settings (1.1–5.6×), with one tie.


We hope the LLM results, the Lean files and the new evidence resolve your concerns, and we would be grateful if you would consider raising your score. If any concern remains, please let us know, and we will be glad to address it before the discussion closes.

Dear Reviewer 1dH4,

Thank you for your careful review of our paper, and for the time and effort you contribute to the community. We understand this is a busy period, but as the author–reviewer discussion closes on November 18, we would be grateful to know whether our responses have addressed your concerns. In brief, the Lean files are now public and rebuild cleanly, and, on LLM reasoning answers, the growing constant you noted is small in practice (see the new Sec. 7). If any concern remains, we would be happy to address it before the discussion closes.

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

This paper studies exact probability powering from samples alone: given IID samples from an unknown discrete distribution pp, the goal is to sample from qk(i)=pik/∑jpjkq_k(i)=p_i^k/\sum_j p_j^k for a fixed integer k≥2k\geq 2, without knowing the probabilities or the support. Classical rejection sampling is exact but requires Θ(nk−1)\Theta(n^{k-1}) samples on nn equally likely outcomes, while returning the first kk-fold collision requires only Θ(n1−1/k)\Theta(n^{1-1/k}) samples but is biased.

The authors propose Collision-map CFTP, which constructs a random map from the first kk-fold collision and the other labels observed before it. They show that this map is reversible with stationary distribution qkq_k, and use coupling from the past to obtain an exact sample. The algorithm requires Ok(1/∥p∥k)O_k(1/\|p\|_k) samples in expectation, matching the collision scale. They also prove an instancewise lower bound: every universal exact sampler must have seen its returned label at least kk times before stopping. Thus, the proposed method is instance-optimal up to a factor depending only on kk.

For k=2k=2, the expected cost is less than 1111 times the first-collision cost, and this factor approaches 8/38/3 on large uniform inputs. The results are supported by simulations, and the authors state that all theorems are formally verified in Lean 4.

Critical strengths

The paper studies an interesting theoretical problem of exact probability powering using only samples, without access to the underlying probabilities or support. The main theoretical result is interesting, as the proposed method achieves collision-scale sample complexity while maintaining exactness. The authors also establish a matching lower bound, showing that the method is instance-optimal up to a constant factor depending on kk. Overall, the paper is well organized and easy to follow, with detailed theoretical analysis and formal verification in Lean 4.

Critical weaknesses

Weaknesses.

While the theoretical results are interesting, I have several concerns about the significance and practical impact of this work.

First, the proposed method builds on existing techniques from collision-based sampling, reversible Markov chains, and coupling from the past. Although the collision-map construction is interesting, the paper could better clarify its technical novelty relative to prior exact-sampling frameworks, particularly Dice Enterprise.

Second, the empirical evaluation is quite limited. Despite motivating the problem through LLM reasoning and answer-level sharpening, the experiments only consider synthetic distributions. It remains unclear whether the theoretical improvements in sample complexity translate into meaningful practical benefits for real LLM inference.

Finally, the guarantees are restricted to fixed integer powers and IID samples, and the dependence on kk can be unfavorable. These limitations reduce the broader applicability of the proposed approach.

Questions for authors

I still have several questions about the novelty and practical significance of this work. First, I would like the authors to clarify the main technical differences between the proposed method and existing exact-sampling approaches, particularly Dice Enterprise, and explain why previous methods cannot achieve similar guarantees. Second, while the paper is motivated by LLM reasoning and answer-level sharpening, the experiments are limited to synthetic distributions. It would be helpful to see whether the theoretical improvement in sample complexity translates into meaningful reductions in inference cost or latency on real LLM tasks. I am also curious about how the method performs for larger values of kk or distributions with small effective support, given that the constant factor can grow significantly with kk. In addition, the current analysis focuses on generating a single exact sample under the IID assumption. Can the method reuse samples or intermediate computations to generate multiple outputs more efficiently, and how would it compare with existing batch-based approaches? Finally, it would be useful to discuss whether the method can be extended to noninteger powers or settings with correlated samples.

6 comments
AuthorsOpenReview ↗

Response to Reviewer ipiH (1/3): on real LLM inference, 16–384× fewer generations and up to 4.3× lower latency than exact rejection

We thank the reviewer for finding the theoretical result interesting. Your central concern is "the significance and practical impact of this work". We address it first, with new experiments on real LLM inference, and then every other point (line numbers refer to the revised PDF):

Your concernShort answer
Practical benefit for real LLM inference (W2, Q2)at k=4, 16–384× fewer LLM generations than exact rejection; up to 4.3× lower measured latency
Technical novelty relative to Dice Enterprise (W1, Q1)DE must know the possible outcomes in advance; even then, it costs more than ours in 31 of 32 settings (Part 2)
Dependence on k; small support (W3, Q3)about 1.2× the lower bound on the typical MATH500 problem (7B); on 1.5B answers it grows with k more slowly than rejection's (Part 3)
Sample reuse? batch methods? (Q4)yes: continuing the chain gives one more exact-law sample per block, 2–4× cheaper per effective sample on a uniform law over 64 labels, and no sample is wasted; CALM's batch method is biased, and at 64 generations its bias is still 0.012, vs our exact 28 (Part 3)
Only integer powering? (W3, Q5)every real power ≥2 is exact: our sampler replaces the bottleneck stage of CALM's exact two-stage scheme (Part 3)
Significance?Theoretical significance: it settles the cost of exact sample-only powering on every input (Part 2)

1. Real LLM inference: 16–384× fewer generations, up to 4.3× lower latency (W2, Q2)

(W2) ... the experiments only consider synthetic distributions. It remains unclear whether the theoretical improvements ... translate into meaningful practical benefits for real LLM inference.
(Q2) ... meaningful reductions in inference cost or latency on real LLM tasks.

We repeat an experiment in which prior work found sharpening useful for reasoning (L461–464):

  • Power sampling (Karan & Du, ICLR 2026) samples p4p^4 of whole generations on MATH500 with Qwen2.5 models and nearly matches RL post-training.
  • Marginal sharpening (Arzhantsev et al., 2026) targets exactly our q4q_4 on MATH-500 answers, and is more accurate than standard sampling (0.90 vs 0.81 for Qwen3-1.7B).

Both need token probabilities and are approximate. We sample the same target in the same setting (MATH500, Qwen2.5, k=4), exactly and from generations alone, adding AIME 2024/25 and a smaller model (7B, 1.5B: Qwen2.5-7B/1.5B-Instruct).

Algorithm 1 runs unchanged on LLM answers (table in the General Response): one sample is one generation (temperature 1, no top-p or top-k truncation) reduced to its final answer, and the cost NN is the number of generations. Only samples are available, since an answer's probability is "an intractable sum over the reasoning paths that reach it".

(a) Inference cost: the saving grows with k. LLM generations per exact output, averaged over problems; lower is better.

ours / rejectionk=2k=3k=4k=5
7B, MATH500 (500 problems)4.7 / 5.812 / 4128 / 43659 / 5,635
7B, AIME 2024/25 (60)16 / 3465 / 687190 / 14,666477 / 3.3e5
1.5B, MATH500 (500)12 / 2742 / 734111 / 42,476260 / 3.2e6

To average over many runs, samples are redrawn at random from each problem's pre-recorded generations, so the costs are those of each problem's observed answer frequencies. Rejection compared here is the stronger early-abort variant (L64–65).

(b) Latency: up to 4.3× lower. Wall-clock time to the first exact output with live generation on a GPU (k=4). Both methods read the same stream of generations, so each problem gives a paired comparison; the speed-up is the per-problem ratio of the two times, averaged over problems. Unfinished runs (because we capped each run's time budget) count as taking the whole time limit; rejection fails to finish far more often (column "Finished"), so without the time cap the speed-ups would likely be even higher.

Model: problems‡ (time cap)Finished: ours / rej.Median time: ours / rej.Mean speed-up [95% CI]
1.5B: 50 MATH500 problems (300 s)49 / 3224 s / 56 s3.0× [2.1, 4.2]
1.5B: 30 "diffuse" problems†29 / 1257 s / >300 s4.3× [2.9, 6.0]
7B: 40 MATH500 and AIME problems (480 s)32 / 2278 s / 242 s1.9× [1.4, 2.5]
7B: 22 "diffuse"14 / 4333 s / >480 s2.3× [1.5, 3.2]
Both models: 16 "concentrated" problems†16 / 16equal1.00×

†Diffuse: the most frequent answer has <30% of the generations; concentrated: >70%.

‡Chosen in advance to cover diffuse, intermediate and concentrated problems. Median time: by then half of the problems had an exact output; ">300 s": fewer than half finished within the limit. The sampler's bookkeeping is negligible; it takes <0.5 ms per output.

Savings come from problems with diffuse answers (harder problems, weaker models); on confident ones both exact methods need only 5–7 generations.

AuthorsOpenReview ↗

Response to Reviewer ipiH (2/3): Dice Enterprise must know the possible outcomes and costs up to 5.6× more; our bounds settle the cost of exact powering

2. Dice Enterprise must know the possible outcomes; ours does not and costs less (W1, Q1)

(W1) ... could better clarify its technical novelty relative to prior exact-sampling frameworks, particularly Dice Enterprise.
(Q1) ... the main technical differences ... particularly Dice Enterprise, and explain why previous methods cannot achieve similar guarantees.

DE must know the possible outcomes before it starts. Ours knows neither the outcomes nor their probabilities. Your summary already names this difference: we sample "without knowing the probabilities or the support". Our related-work paragraph states it (L120–123), and, for your convenience, our revision expands the comparison in App. C.1 (L1395–1422):

Dice Enterprise (Morina et al., AAP 2022)Collision-map CFTP
Possible outcomesknown, finite (nn faces)unknown, possibly countably infinite
State space for pkp^kladder of n(n+k−2k−1)n\binom{n+k-2}{k-1} monomialsobserved labels only
One step usesone roll (moves to an adjacent monomial)one collision block (a repeat anywhere in it counts)
Coalescence check, >2 faces"not necessarily monotonic": track all statesjust an empty exception dictionary
Cost guaranteegrows with nn (Prop. 3.10: ≥n4k−2−1\ge n^{4k-2}-1 on a fair die)at most a factor CkC_k, depending only on k, times the lower bound μk\mu_k, on every input
Lower boundnonematching, on every input

DE's authors say it stays practical only when the polynomials have low degree and the die has few faces (Sec. 3.3).

Even when outcomes are known, DE costs more. Samples per output on fair nn-sided dice (DE: its authors' R package with its best ladder):

k=2: DE / ours / rejectionk=3: DE / ours / rejection
n = 414.2 / 8.7 / 865 / 36 / 36
n = 826.9 / 12.8 / 16227 / 58 / 136
n = 1135.1 / 14.7 / 22391 / 70 / 253

Across 32 settings (fair and skewed dice with 2–12 faces, k=2–4), DE costs more than ours in 31, from 1.1× (n=3, k=4) to 5.6× (n=11, k=3); the remaining one is a tie (n=2, k=4: 46.1 vs 46.5). Over n ≤ 12, DE's cost grows like n0.87n^{0.87} (k=2) and n1.66n^{1.66} (k=3), close to rejection's nn and n2n^2; ours follows n1/2n^{1/2} and n2/3n^{2/3}.

Earlier methods cannot give our guarantee. Rejection-type Bernoulli factories wait for k consecutive agreements, costing Θ(1/Sk)\Theta(1/S_k) with Sk=∑jpjkS_k=\sum_jp_j^k, i.e. nk−1n^{k-1} on uniform inputs. DE also advances one roll at a time, and its bound depends on the number of outcomes. Collision-based methods (Aggarwal et al., 2015; CALM's batch method) are approximate. Ours is the first sampler that is both exact and at the collision scale, and Thm 2 shows that no universal exact sampler can beat that scale. The new ingredients are (i) the collision map and its renaming proof of reversibility (Sec. 4.2), (ii) the default-plus-exceptions representation that lets CFTP run on an unknown countable space (Sec. 4.3), and (iii) the k-block intersection bound that removes all support dependence (Lemma 3).

3. Significance: our bounds settle the cost of exact powering on every input

On significance, your review already states the result: the method "achieves collision-scale sample complexity while maintaining exactness" and is "instance-optimal up to a constant factor depending on kk". We agree that the contribution is mainly theoretical, and we see this as its strength: it settles the cost of exact sample-only powering on every input. Comparable results for basic sampling primitives have become the standards of their problem classes: a fair coin from a biased one (von Neumann, 1951), coupling from the past (Propp & Wilson, RSA 1996), fast coin transformations (Nacu & Peres, AAP 2005), exact maps of a known die (DE, AAP 2022) and diffusion sampling guarantees, theory only (Chen et al., ICLR 2023, oral).

Our result plays this role for powering: any future sample-only exact method can be measured against μk\mu_k. Unlike most works above, it also has direct uses; besides LLM reasoning (Part 1), our paper states:

  • Generators that give only samples: diffusion LMs, whose likelihoods are only bounded or estimated (L1485–1488); simulators and probabilistic programs, whose output probabilities sum over executions (L43–45, L1460–1464).
  • Exact references that keep Monte Carlo averages unbiased and measure the bias of approximate sharpening (L57–59, L523–527), as for CALM's batch method in Part 3.
  • Exact low temperatures for every real power ≥ 2 (L531–533), replacing the rejection stage of CALM's exact sampler (L1480).
  • Marginal MAP estimation by powering an intractable marginal posterior (L1465–1466), and distillation targets when a teacher exposes only its outputs (L523–524).
AuthorsOpenReview ↗

Response to Reviewer ipiH (3/3): the k-factor is small in practice; several outputs waste no samples; every real power ≥ 2 is exact

4. The k-factor is small on practical inputs, and small supports are cheap (W3, Q3)

(W3) ... the dependence on kk can be unfavorable.
(Q3) ... larger values of kk or distributions with small effective support, given that the constant factor can grow significantly with kk.

We agree that the proven constant grows quickly with k, and the paper says so (L1125–1126). On practical inputs, however, the factor is small, and every exact sampler we measured shows some growth in k.

Median cost divided by the lower bound μk\mu_k of Theorem 2 (details in the new App. E, L1512–1571, which covers k ≤ 8):

k=2k=3k=4k=5growth per +1 in k (fit)
Ours, 7B answers, MATH5001.121.181.241.30×1.05
Ours, 1.5B answers, MATH5002.212.953.784.80×1.29
Ours, 24 synthetic distributions (App. E)2.333.605.448.03×1.51
Exact rejection, same 1.5B answers2.454.518.5916.9×1.91
DE, fair 4-sided die (outcomes known)4.4211.116.4–×1.92
Gambler's ruin, fair coin (outcomes known)1.602.182.753.32×1.27
  • Parameter-dependent constants are standard in celebrated theory results, e.g., the instance-optimal threshold algorithm, whose ratio grows with the number of lists and cannot be improved (Fagin, Lotem & Naor; Gödel Prize 2014); learning mixtures of k Gaussians, at a cost that must be exponential in k (Moitra & Valiant, FOCS 2010); and Rényi-entropy estimation at our collision scale, Θ(n1−1/k)\Theta(n^{1-1/k}) samples with k-dependent constants (Acharya et al., IEEE TIT 2017).
  • Small effective support is cheap for both methods, and rejection can then be slightly cheaper, as our footnote (L215) and App. B.1 state: 5.4 vs 4.9 generations at k=4 on MATH500 problems whose top answer has >70% mass (7B; Table 3, L1642).
  • No need to know in advance which method is cheaper. For practical use, a simple exact hybrid picks our sampler or rejection for each output using only the samples of earlier outputs, so every output stays exact and independent. On 1,060 LLM answer distributions it costs on average only about 1% more than the cheaper method.

5. The chain can be reused and no sample is wasted; CALM's batch method stays biased (Q4)

(Q4) Can the method reuse samples or intermediate computations to generate multiple outputs more efficiently, and how would it compare with existing batch-based approaches?

Yes, and every output stays exact, unlike with CALM's batch method.

  • No sample is wasted. Each run ends at a stopping time, so leftover samples are fresh IID inputs for the next output, and m outputs are independent and exact. Our latency runs in Part 1 used batched generation this way.
  • Reusing the chain costs one block per further sample. After one exact output, each further fresh block gives another sample with law exactly qkq_k (dependent on the previous one), instead of the E[T]\mathbb E[T] blocks that a fresh exact output needs: 2–4× cheaper per effective sample on a uniform law over 64 labels.
  • CALM's batch method is biased at every batch size; ours is exact at 28 generations (real answers, 7B, MATH500, k=4):
MethodGenerations / outputBias (total variation to q4q_4)
First collision6.20.034
CALM batch method, batch size 16 / 64 / 25616 / 64 / 2560.038 / 0.012 / 0.003
Exact rejection4360
Collision-map CFTP280

On diffuse problems, CALM's bias is 0.25 / 0.08 / 0.024 at batch size 16 / 64 / 256, while ours is exact at 173 generations.

6. Every real power ≥ 2 is exact, and IID holds exactly here (W3, Q5)

(W3) ... the guarantees are restricted to fixed integer powers and IID samples ...
(Q5) ... whether the method can be extended to noninteger powers or settings with correlated samples.

  • Every real power α ≥ 2 is exact. Write α=k+β with β∈[0,1), draw x∼qkx\sim q_k with our sampler, and accept it with probability pxβp_x^\beta by Mendo's (2019) Bernoulli factory, whose coin is "a fresh sample equals x". This is CALM's exact two-stage scheme with our sampler in its integer stage, now stated in Sec. 8 (L531–533; App. C.3, L1470–1480); CALM names this stage as its low-temperature bottleneck (L1473–1474). For non-integer α on n equally likely labels, it cuts the cost from order nα−1n^{\alpha-1} to order max⁡(nα−k+1−1/k,n)\max(n^{\alpha-k+1-1/k}, n).
  • IID holds exactly here: independent generations for a fixed prompt, as in self-consistency. IID is also the standard input model of exact transformations (von Neumann's coin, Bernoulli factories, DE).

We hope these address your concerns about practical impact and novelty. If so, we would be grateful if you would reconsider your score. If any concern remains, please let us know, and we will be glad to address it before the discussion closes.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response: experiments show exact powering of LLM answers with 16–384× fewer generations; k-factor is small in practice; Lean code is provided

We thank the reviewers, who all value the theory and ask what it offers in practice: "the significance and practical impact of this work" (ipiH), "the practical implications of the instance-optimality guarantee" (1dH4), and uses "of particular interest to an ICLR audience" (d2EW). We therefore ran our sampler, unchanged, on an LLM reasoning task on which prior work found powering useful. From generations alone, without likelihoods or a list of possible answers, it draws exact samples of the sharpened answer distribution with 16–384× fewer LLM generations than exact rejection and up to 4.3× lower latency.

The table answers the five main questions:

QuestionAsked byShort answer
Does it help real LLM inference?all threeYes. At k=4 on MATH500 and AIME (Qwen2.5): 16–384× fewer generations than exact rejection and up to 4.3× lower latency.
Is the k-factor small in practice?all threeYes. For k=2–5, ours costs only 1.1–1.3× the lower bound of Thm 2 on the median MATH500 problem (Qwen2.5-7B), 2.2–4.8× (1.5B), and 2.3–8.0× (medians) on 24 synthetic distributions. The proven CkC_k (up to 1.3e9) is a theoretical worst case.
Is it new relative to Dice Enterprise (DE)?ipiH, 1dH4Yes. DE must know the possible outcomes in advance, and its cost bound grows with the number of possible outcomes. Even when given the possible outcomes, DE uses more samples in 31 of 32 tests and ties in the other — each test is one die (fair or skewed, 2–12 faces) and one power k=2–4.
Can the proofs be checked?1dH4, d2EWYes. Lean 4 code: https://anonymous.4open.science/r/exact-probability-powering-45BE, rebuilt from source with no sorry and only Lean's three standard axioms.
Is exactness limited to integer powers?ipiHNo. Every real power ≥ 2 is exact: our sampler replaces the bottleneck stage of CALM's exact two-stage scheme (Sec. 8, L531–533).

We have uploaded a revised PDF with changes in blue, and all line numbers in our replies, such as L461–464, refer to the revised PDF.

1. On a real LLM task, our sampler needs 16–384× fewer generations than exact rejection

  • We repeat experiments from prior work that found sharpening useful for reasoning (L461–464). Karan & Du (ICLR 2026) sample p4p^4 of whole generations on MATH500 with Qwen2.5 and nearly match RL post-training; marginal sharpening (Arzhantsev et al., 2026) targets our q4q_4 on MATH-500 answers and beats standard sampling. Neither is exact, and both need token probabilities. We keep their setup: MATH500, Qwen2.5 and k=4.
  • It is exactly our paper's setting: the probability of an answer is unknown (it's "an intractable sum over the reasoning paths that reach it", Dohan et al., 2022; Kuhn et al., ICLR 2023), and the possible answers are unknown in advance. Algorithm 1 runs unchanged:
Algorithm 1LLM experiment
draw(), the only access to ppone generation, stripped to its final answer (L45–50)
label comparisonare two answers identical?
collision blockgenerate until some answer has appeared k times
output ∼qk∝pk\sim q_k\propto p^kan exact sample from the sharpened answer distribution
cost NNnumber of LLM generations needed

The results show that our sampler has practical uses and advantages:

OursExact rejection
LLM generations per exact output: Qwen2.5-7B, MATH50028436 (16× more)
... Qwen2.5-1.5B, MATH50011142,476 (384×)
... Qwen2.5-7B, AIME 2024/25 (harder task)19014,666 (77×)
Median time to the first exact output, live generation: Qwen2.5-1.5B, 30 problems with "diffuse" answers (the most frequent answer has <30% probability)†57 s>300 s (12 of 30 finished in 300 s)

†Where the model is confident (>70%), two methods are comparable. This shows savings are largest where answers are spread out. ipiH (Part 1) has the detailed protocol and k=2–5.

2. Ours is not always cheaper than rejection, but a simple exact hybrid gets nearly the best of both

The reviewers were concerned that our sampler may lose its advantage in certain practical applications. For practical use, one can use a simple exact hybrid that picks our sampler or rejection per output from earlier outputs' samples only, so every output stays exact and independent. On 1,060 LLM answer distributions this hybrid method costs on average only about 1% more than the cheaper one.

3. Our key advantage over likelihood-based samplers: no likelihoods needed

Diffusion LMs such as LLaDA-8B give likelihoods only through variational bounds or Monte Carlo estimates (L1485–1488), whereas our sampler needs only their outputs. d2EW (1/2) lists further uses, including those beyond LLMs.


Update: following d2EW's suggestion, we have further revised the paper to include all additional results (see the new Sec. 7, App. F).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.