- 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 with probability the paper considers how to draw samples with probability proportional to (for an integer ). The paper also shows that the expected cost of the method (in terms of number of oracle-calls) is within a -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 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 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 -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 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 -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 , and compare it with the theoretical upper bound.
Some corrections that I spotted: The first listed main contribution says the algorithm 'returns exactly on any countable support' whereas it actually returns samples under distribution . 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
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 (), 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.mdmaps 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 nosorryand only three standard axioms:propext,Quot.soundandClassical.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 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 "
The first listed main contribution says the algorithm 'returns exactly on any countable support' whereas it actually returns samples under distribution . 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 " 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.
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)
Sharpening LLM answers is a current route to better reasoning, and we ran our sampler in the same experiment as prior work (L461–464):
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:
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
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)
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. We measured it on real LLM answer distributions and on 24 non-uniform synthetic distributions (Zipf, heavy-head, dyadic, answer-like, countably infinite geometric):
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 Ck 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).