acceptodds
Withdrawn from ICLR 2027

Deletion Optimality Characterizes Shared Gumbel Sampling

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Shared randomness coordinates categorical samples across different distributions, supporting correlated sampling and counterfactual generation. What makes shared Gumbel sampling a distinguished choice among exact sampling rules? We show that a simple deletion principle determines its entire joint behavior. On a finite alphabet with at least three labels, any exact shared-randomness sampler that max- imizes agreement between every distribution and its one-label deletions has the same finite-dimensional output laws as shared Gumbel sampling. Thus, optimiz- ing agreement on these local pairs uniquely determines the coupling across all distributions. As a consequence, no exact shared-randomness sampler can match or improve Gumbel agreement on every distribution pair and strictly improve it on any pair. The characterization covers arbitrary measurable samplers. Its proof derives a common race representation from deletion optimality and yields quanti- tative certificates relating comparison reversals to deletion deficits. On countably infinite alphabets, we construct distinct deletion-optimal couplings within a com- mon tail class and show that continuity under prefix truncation restores unique- ness. These results establish a local characterization of shared Gumbel sampling and identify the boundary between finite rigidity and countable freedom.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
correlated sampling, shared randomness, Gumbel sampling, maximal coupling, Pareto optimality

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Pn9vOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper shows that Gumbel sampling method could maintain the consistency of the result under deletion. In particular, if we consider generating a sample from a finite state space and use Gumbel sampling, dropping one element from the state space will still give the same realization under the same random seed.

Critical strengths

N/A

Critical weaknesses

This paper is an AI slop. The introduction and abstract are full of incoherent arguments, self-invented composite terms and unnatural pharses. I suggest the authors put some human effort on the paper before submitting it to any human reviewed conference.

I'll cite one paragraph in their introduction as an example:

Line 50-55: "The proof derives a common race representation from agreement constraints on an arbitrary measurable sampler. Deletion optimality first forces the winner to survive every nonwinner deletion. Three-label distributions then connect binary comparisons. If a label wins at lower odds but loses at higher odds, these connections propagate the reversal along a geometric chain. At its endpoints, exact marginal probabilities make that reversal arbitrarily unlikely. Nested binary comparisons yield random thresholds; consistency across triples makes these thresholds ratios of common scores. Finally, exact categorical marginals identify the exponential-ratio law."

As a proof overview shown in the first page, I have no idea about what "race representation", "nonwinner deletion" and " propagate the reversal along a geometric chain" means.

Questions for authors

N/A

2 comments
AuthorsOpenReview ↗

Response to Reviewer Pn9v

Response to Reviewer Pn9v

Thank you for quoting lines 50–55. You are right that the submitted Abstract and Introduction were poorly written and obscured what the paper proves; we rewrote both from scratch in standard terminology (Abstract, lines 11–31; Sec. 1, lines 34–115) so the converse claim—that optimal deletion agreement on at least three labels forces Gumbel's joint law—is clear upfront.

[W1] The Abstract and Introduction contain incoherent arguments, self-invented composite terms, and unnatural phrases.

Response: We rewrote both sections (lines 11–31, 34–115) and standardized notation (Defs. 1–3, Table 1, lines 123–176):

  • Converse claim (lines 16–23, 45–53, 77–80): Under Gumbel sampling G(p)=arg⁡max⁡i(log⁡pi+Γi)=arg⁡min⁡i(Ei/pi)G(p) = \arg\max_i (\log p_i + \Gamma_i) = \arg\min_i (E_i/p_i) (eq. (2)), deleting an unsampled label preserves the output (eq. (4)). Theorem 1 (lines 181–190) proves the converse: on n≥3n \ge 3 labels, any exact sampler attaining 1−pi1 - p_i on deletion pairs (p,p−i)(p, p^{-i}) has GG's joint law on finite input lists (unlike inverse-CDF, weighted MinHash, or hierarchical P-MinHash, Fig. 1b; fails at n=2n=2 and on N\mathbb{N} without truncation continuity, lines 198–200, 446–458).
  • Standard terms: the coined phrases flagged in [W2] are replaced by standard terms (table below). All proofs were verified line by line by the authors; AI use is disclosed per ICLR policy (lines 568–574).

[W2] In the proof overview (lines 50–55), "race representation", "nonwinner deletion", and "propagate the reversal along a geometric chain" are not understandable.

Response: Submitted lines 50–55 were opaque; we replaced those phrases and rewrote the passage as a five-step "Proof roadmap" (Sec. 1, lines 104–115; Fig. 2, lines 270–285):

Submitted phraseReplacement & location
"race representation"Random-utility form F(p)=arg⁡min⁡i(τi/pi)F(p)=\arg\min_i (\tau_i/p_i) (eq. (11), lines 335–338)
"nonwinner deletion"Deleting an unsampled label: F(p)≠i⇒F(p−i)=F(p)F(p)\ne i \Rightarrow F(p^{-i})=F(p) a.s. (Lemma 1, lines 253–260)
"propagate the reversal..."Chain of 2m2m three-label inputs bounding a reversal (Lemma 3, Fig. 2, lines 270–285, 308–321)

Before (submitted lines 50–55):

The proof derives a common race representation from agreement constraints on an arbitrary measurable sampler. Deletion optimality first forces the winner to survive every nonwinner deletion. Three-label distributions then connect binary comparisons. If a label wins at lower odds but loses at higher odds, these connections propagate the reversal along a geometric chain. At its endpoints, exact marginal probabilities make that reversal arbitrarily unlikely. Nested binary comparisons yield random thresholds; consistency across triples makes these thresholds ratios of common scores. Finally, exact categorical marginals identify the exponential-ratio law.

After (revised Sec. 1 "Proof roadmap", lines 104–115):

Proof roadmap. Fix an arbitrary exact sampler FF with optimal deletion agreement. (1) Deleting an unsampled label keeps the output: optimal agreement on (p,p−i)(p, p^{-i}) is equivalent to "if F(p)≠iF(p) \neq i then F(p−i)=F(p)F(p^{-i}) = F(p)" almost surely (Lemma 1). (2) Pairwise comparisons are transitive: on a three-label input, the sampled label also wins both two-label comparisons obtained by deleting one of the other labels, so these comparisons never form a cycle. (3) Two-label comparisons are monotone: if FF picks ii over jj when the odds of ii against jj are rr, it also picks ii at any higher odds ss, almost surely (Lemma 3). To prove this, Lemma 3 places ii, jj and a third label kk in a chain of three-label inputs that share two-label comparisons; a reversal forces one of two events whose probabilities exactness makes arbitrarily small (Figure 2). (4) Random-utility form: monotonicity gives random thresholds, and transitivity makes them ratios τi/τj\tau_i / \tau_j of random clocks τi\tau_i that do not depend on the input. Step (1) then gives F(p)=arg⁡min⁡iτi/piF(p) = \arg\min_i \tau_i / p_i for every input. (5) The clocks are exponential: exactness at every input forces (τj/τn)j<n(\tau_j / \tau_n)_{j < n} to have the law of ratios of independent Exp(1)\mathrm{Exp}(1) variables, which is the Gumbel sampler.

Thank you again for this feedback.

I thank the reviewer's thoughtful response and all the extra effort they have made. However, my concerns about the readability still remains. The response and the revised content still seems to be heavily AI-generated and has low quality. To justify my argument, I would like to use their modified abstract as a concrete example.

Line 11-16: "A shared-randomness sampler maps a probability distribution pp on a set of labels, together with a random seed, to a label distributed according to pp. When one seed is used for every input, the outputs for different inputs are coupled, and the probability that two inputs produce the same label (their agreement) is what matters in correlated sampling, counterfactual generation, watermarking and drafterinvariant speculative decoding. "

"shared-randomness" is irrelevant to the definition of sampler in the first sentence and the definition of "shared-randomness sampelr" is never explicitly given in the main text of this paper and such a term shows up in the first sentence of the abstract and the core theorem placed in the first page.

"one seed is used for every input" is also vague and the motivation of "two inputs produce the same label (their agreement) is what matters" is not clearly justified. The implication here is: "Let A(s,P)\mathcal{A}(s, P) be a sampler take a random seed and a target distribution as input, when ss is randomly drawn from a (rather easier) distribution, the distribution of the output of A(s,P)\mathcal{A}(s, P) is PP. In practice, when PP and QQ are close, we expect the sampler A\cal{A} have some level of consistency: When A\mathcal{A} use the same seed ss to draw from PP and QQ, the output should agree with each other more. Such consistency is usefuly and has wide applications on other fields..."

It takes siginificant amount of intermediate reasoning to understand those narratives and such efforts in my opinion is not necessary for understanding the content. Such issues should be carefully resolved by human rewriting and understanding before the paper being submitted to any human-reviewed conference.

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

The paper studies how to sample from many categorical distributions with one shared random seed, so that the samples for different distributions agree as often as possible. This is used in correlated sampling, counterfactual text generation (Ravfogel et al., 2025) and drafter-invariant speculative decoding (Daliri et al., 2025).

A sampler F(p,ω)F(p,\omega) maps a distribution pp on nn labels and a seed ω\omega to a label. It is exact if P(F(p)=i)=pi\mathbb P(F(p)=i)=p_i for every pp. The same seed is used for every pp, and the agreement of two inputs is aF(p,q)=P(F(p)=F(q))a_F(p,q)=\mathbb P(F(p)=F(q)). The standard choice is shared Gumbel-max, G(p)=arg⁡min⁡iEi/piG(p)=\arg\min_i E_i/p_i, where the seed is E1,…,EnE_1,\dots,E_n iid Exp(1)\mathrm{Exp}(1).

Main result. Let p−ip^{-i} be pp with label ii deleted and renormalized. Every exact sampler has aF(p,p−i)≤1−pia_F(p,p^{-i})\le 1-p_i, and GG attains this bound. A sampler that attains it for every pp and ii is called deletion-optimal. Theorem 1: for n≥3n\ge 3 labels, any deletion-optimal exact sampler has the same joint output distribution as GG on every finite set of inputs. As a corollary (Cor 2), any exact sampler with a different joint output distribution is strictly worse than GG on some pair (p,p−i)(p,p^{-i}), so no exact sampler Pareto-dominates GG.

Extensions.

  • Robustness (Section 5). If FF is close to deletion-optimal on a suitable finite set of 3-label distributions, then its agreement on a given pair of 2-label distributions is close to that of GG (Theorem 4).
  • Countable alphabets (Section 6). Theorem 1 fails here, and the paper gives explicit counterexamples. Uniqueness is restored by adding truncation continuity: F(TMp)→F(p)F(T_Mp)\to F(p) in probability as M→∞M\to\infty, where TMpT_Mp is pp restricted to its first MM labels and renormalized (Theorem 6).
Critical strengths

1. Strong characterization.
For n≥3n\ge 3, optimal agreement on deletion pairs alone fixes the whole joint law of the sampler. The proof allows any measurable FF. It first shows that FF must pick arg⁡min⁡iSi/pi\arg\min_i S_i/p_i for random scores SiS_i that do not depend on pp, and then that exactness forces (S1/Sn,…,Sn−1/Sn)(S_1/S_n,\dots,S_{n-1}/S_n) to have the same distribution as (E1/En,…,En−1/En)(E_1/E_n,\dots,E_{n-1}/E_n) for iid exponentials. The key step (Lemma 3) uses a chain of 3-label distributions to show that if FF outputs ii on the 2-label distribution on i,ji,j with odds pi/pj=rp_i/p_j=r, it also outputs ii at any higher odds (almost surely). The argument is short and could be useful elsewhere.

2. The main theorem is sharp and robust. With infinitely many labels, the counterexamples show that deletion optimality alone is not enough, and Theorem 6 shows that adding truncation continuity is exactly what is needed. For n=2n=2, every deletion leaves a single label, so deletion pairs carry no information. The paper explains this and proves the Pareto result for n=2n=2 directly.

Section 5 further shows robustness: near-optimal deletion agreement on a finite chain of 3-label distributions gives near-Gumbel agreement on the corresponding pair of 2-label distributions.

Critical weaknesses

1. Missing prior work.
The paper presents Pareto optimality of GG as an open question of Daliri et al. (2025) and claims to settle it. It also credits Daliri et al. with showing that GG has higher agreement than weighted MinHash. Both results are in Moulton & Jiang (2018), which is not cited. Their P-MinHash, arg⁡min⁡i−log⁡h(i)/xi\arg\min_i -\log h(i)/x_i with h(i)h(i) iid uniform on (0,1](0,1], is exactly GG, so their JPJ_P equals aGa_G. Their Theorem IV.4 shows that GG is Pareto optimal, and Theorem IV.5 that JPJ_P is at least the agreement of weighted MinHash.

Since Pareto optimality is already known, the paper should present its contribution as follows.

  1. Optimal agreement on deletion pairs alone already forces the law of GG.
  2. The conclusion is stronger. Moulton & Jiang imply only that a sampler with aF≥aGa_F\ge a_G on all pairs has aF=aGa_F=a_G. Corollary 2 shows that such a sampler has the same joint distribution as GG.
  3. The results of Sections 5 and 6 are new.

The paper should also compare Corollary 2 with Theorem IV.4 of Moulton & Jiang, which says more about where a sampler loses. If FF has higher agreement than GG on a pair (x,y)(x,y), then FF has lower agreement than GG on some pair (x,z)(x,z) or (y,z)(y,z), and on that pair GG agrees at least as often as on (x,y)(x,y). Corollary 2 only says that FF is worse than GG on some deletion pair, with no link to the pair where FF is better.

References R. Moulton and Y. Jiang. Maximally Consistent Sampling and the Jaccard Index of Probability Distributions. In IEEE International Conference on Data Mining Workshops (ICDMW), 2018. arXiv:1809.04052.

Questions for authors

Clarifications:

  1. How do Theorem 1 and Corollary 2 relate to Theorems IV.4–IV.5 of Moulton & Jiang (2018)? Which parts of Corollary 2 are new? I think the results: deletion pairs alone suffice, and the full joint law is forced, are new.

  2. Does Pareto optimality on countable alphabets follow from Theorem 6? If an exact FF has aF≥aGa_F\ge a_G on all pairs in Δ(N)\Delta(\mathbb N), it is deletion-optimal, since aG(p,p−i)=1−pia_G(p,p^{-i})=1-p_i. It is also truncation continuous, since for every MM with ∑k≤Mpk>0\sum_{k\le M}p_k>0, P(F(TMp)=F(p))≥aG(TMp,p)=∑k≤Mpk→1.\mathbb P(F(T_Mp)=F(p))\ge a_G(T_Mp,p)=\sum_{k\le M}p_k\to 1. Theorem 6 then gives that FF has the joint law of GG. Is this correct? If so, it is worth stating. It would also extend Theorem IV.4 of Moulton & Jiang, which is proved only for finitely many labels and gives only equal agreements.

2 comments
AuthorsOpenReview ↗

Response to Reviewer sGmB (Part 1/2)

Response to Reviewer sGmB (Part 1/2)

Thank you for pointing us to Moulton & Jiang (2018), clarifying how our results relate to Theorems IV.4–IV.5, and noting the countable Pareto deduction from Theorem 6. We now cite and credit Moulton & Jiang (2018) for finite pairwise Pareto optimality and weighted-MinHash domination, updated Daliri et al. (2025), and structured the Abstract and Introduction around your three points ([W1]–[W2]). To answer [W3] on where a sampler loses when it beats Gumbel, we added a brief helper result (Proposition 3, lines 222–229) complementing Theorem IV.4 via their bridge zℓz^\ell.

[W1] Cite Moulton & Jiang (2018), whose P-MinHash equals GG, whose Theorem IV.4 proves finite pairwise Pareto optimality, and whose Theorem IV.5 proves domination over weighted MinHash; correct the attribution to Daliri et al. (2025).

Response: We cite and credit Moulton & Jiang (2018) for Theorems IV.4–IV.5 and update the attribution to Daliri et al. (2025) (Abstract, line 24; Sec. 1, lines 82–86; Sec. 3, lines 208–214; Sec. 7, line 466; Supp. B.3, supp. lines 141–164).

  • P-MinHash arg⁡min⁡i(−log⁡hi)/xi\arg\min_i (-\log h_i)/x_i (hi∼i.i.d.Unif(0,1)h_i \overset{\text{i.i.d.}}{\sim} \mathrm{Unif}(0,1)) equals GG via Ei=−log⁡hi∼Exp(1)E_i = -\log h_i \sim \mathrm{Exp}(1), so JP=aGJ_P = a_G (Thm II.1; lines 138–145, 209–210).
  • Moulton & Jiang proved finite pairwise Pareto optimality (Thm IV.4) and JW≤aGJ_W \le a_G (Thm IV.5) for weighted MinHash JWJ_W; Angel & Spinka (2019) and Daliri et al. (2025) later reproved JW≤aGJ_W \le a_G, and Daliri et al. posed Pareto optimality as open in speculative decoding (lines 82–86).

[W2] Present the paper's contributions clearly around: (1) deletion pairs alone force the law of GG; (2) equality holds for the full joint distribution, not just pairwise agreements; and (3) Sections 5 and 6 are new.

Response: The Abstract (lines 20–31) and Sec. 1 (lines 88–102) organize the paper around these three points, plus two brief additions (Prop. 3, Cor. 7) answering your questions:

DimensionMoulton & Jiang (2018), Thm IV.4This paper
HypothesisaF≥aGa_F \ge a_G on all pairs (p,q)(p, q)Optimal agreement on deletions (p,p−i)(p, p^{-i}) alone (n≥3n \ge 3; Thm 1, Cor. 2a)
ConclusionEqual pairwise agreements (aF=aGa_F = a_G)Equal full joint law of (F(p1),…,F(pM))(F(p^1), \dots, F(p^M)) (Thm 1, Cor. 2b)
AlphabetFinite onlyFinite (n≥3n \ge 3, Thm 1; all finite nn, Cor. 2b) & countable (N\mathbb{N}, Thm 6, Cor. 7)
StabilityNot addressedQuantitative deficit bounds (Thm 4, Prop. 5) & 4-pair bound (Prop. 3)

Equality of joint laws is strictly stronger than equal pairwise agreements, since P(F(p)=F(q))\mathbb{P}(F(p)=F(q)) does not fix P(F(p)=i,F(q)=j)\mathbb{P}(F(p)=i, F(q)=j) (lines 211–213).

[W3] Compare Corollary 2 with M&J Theorem IV.4 regarding where a sampler loses when it beats GG on some pair (p,q)(p, q), since Corollary 2 alone does not link the losing deletion pair to (p,q)(p, q).

Response: To answer this, we added a short helper result (Prop. 3, eqs. (6)–(7), lines 215–246; Supp. B, supp. lines 111–164) complementing Theorem IV.4: using their bridge zℓz^\ell, it bounds any label-level gain on (p,q)(p, q) by restriction deficits on four explicit pairs from p,q,zℓp, q, z^\ell, which on finite sets decompose along deletions into Theorem 1's deficits (lines 226–229).

For exact FF, (p,q)(p, q), and ℓ∈supp⁡p∩supp⁡q\ell \in \operatorname{supp} p \cap \operatorname{supp} q, let Aℓp={i:piqℓ≥qipℓ}A^p_\ell = \lbrace i : p_i q_\ell \ge q_i p_\ell \rbrace, Aℓq={i:piqℓ≤qipℓ}A^q_\ell = \lbrace i : p_i q_\ell \le q_i p_\ell \rbrace, and zℓ∝max⁡(p/pℓ,q/qℓ)z^\ell \propto \max(p/p_\ell, q/q_\ell) (zℓℓ=Jℓ(p,q)z^\ell_\ell = J_\ell(p,q)). With D(ν,S)=ν(S)−aF(ν,ν∣S)≥0D(\nu, S) = \nu(S) - a_F(\nu, \nu\vert_S) \ge 0, P(F(p)=F(q)=ℓ)≤Jℓ(p,q)+D(p,Aℓp)+D(q,Aℓq)+D(zℓ,Aℓp)+D(zℓ,Aℓq).\mathbb{P}\bigl(F(p) = F(q) = \ell\bigr) \le J_\ell(p, q) + D(p, A^p_\ell) + D(q, A^q_\ell) + D(z^\ell, A^p_\ell) + D(z^\ell, A^q_\ell).

  • Mechanism (lines 230–240): Since zℓ∣Aℓp=p∣Aℓpz^\ell\vert_{A^p_\ell} = p\vert_{A^p_\ell} and zℓ∣Aℓq=q∣Aℓqz^\ell\vert_{A^q_\ell} = q\vert_{A^q_\ell}, if F(p)=F(q)=ℓF(p)=F(q)=\ell and none of the four restrictions alters a surviving winner, then F(zℓ)=ℓF(z^\ell)=\ell (probability Jℓ(p,q)J_\ell(p,q)).
  • Complementary comparison (lines 241–246; Supp. B.3, supp. lines 157–163): Theorem IV.4 finds a losing pair (p,z)(p, z) or (q,z)(q, z) with aG≥aG(p,q)a_G \ge a_G(p, q) via finite-set bridge induction; Proposition 3 is complementary, charging gains on (p,q)(p, q) to four restriction pairs where GG attains 1−dTV1 - d_{\mathrm{TV}} (finite and countable sets).
AuthorsOpenReview ↗

Response to Reviewer sGmB (Part 2/2)

Response to Reviewer sGmB (Part 2/2)

For [Q1], both parts of Corollary 2 you identified are new—sufficiency of single-label deletion pairs on n≥3n \ge 3 labels (Theorem 1, Corollary 2(a)) and equality of the full joint output law across inputs (Corollary 2(b))—while finite pairwise Pareto optimality and domination over weighted MinHash are credited to Moulton & Jiang (2018). For [Q2], as Reviewer sGmB observed, global domination aF≥aGa_F \ge a_G on countable alphabets implies both deletion optimality and truncation continuity, so Theorem 6 yields countable Pareto optimality with equality of joint laws; we added this three-line deduction as a short corollary (Corollary 7, Sec. 6, lines 432–445).

[Q1] How do Theorem 1 and Corollary 2 relate to Theorems IV.4–IV.5 of Moulton & Jiang (2018), and which parts of Corollary 2 are new?

Response: Yes—both parts you identify are new, namely sufficiency of single-label deletion pairs for n≥3n \ge 3 (Theorem 1, lines 181–190; Corollary 2(a), lines 201–203) and equality of the full joint law (Corollary 2(b), lines 203–214), whereas finite pairwise Pareto optimality (Theorem IV.4) and domination over weighted MinHash (Theorem IV.5) belong to Moulton & Jiang (2018) (lines 82–86, 208–214; Supp. B.3, supp. lines 141–164).

  • Corollary 2(a) (lines 201–203, 206, 213–214): For n≥3n \ge 3, any exact sampler without Gumbel's joint law loses strictly on some single-label deletion pair (p,p−i)(p, p^{-i}), where Gumbel attains the coupling ceiling 1−pi=1−dTV(p,p−i)1 - p_i = 1 - d_{\mathrm{TV}}(p, p^{-i}) (whereas n=2n = 2 admits non-Gumbel deletion-optimal couplings; lines 198–200, 207–208; Supp. A.4, supp. lines 90–100).
  • Corollary 2(b) (lines 203–213): For every finite nn, an exact sampler with aF≥aGa_F \ge a_G on all pairs has Gumbel's joint law (F(p1),…,F(pM))=d(G(p1),…,G(pM))(F(p^1), \dots, F(p^M)) \overset{d}{=} (G(p^1), \dots, G(p^M)); for n≥3n \ge 3, domination on single-label deletion pairs alone suffices by Theorem 1.
  • Link to Proposition 3 (lines 222–229; Supp. B.2, supp. lines 134–139): Proposition 3 complements Corollary 2(a) and Moulton & Jiang's Theorem IV.4 by charging any gain on (p,q)(p, q) to four restriction deficits that decompose along single-label deletions of pp, qq, and zℓz^\ell.

[Q2] Does Pareto optimality on countable alphabets follow directly from Theorem 6, since aF≥aGa_F \ge a_G implies both deletion optimality and truncation continuity?

Response: Yes—as Reviewer sGmB observed, global domination aF≥aGa_F \ge a_G on Δ(N)\Delta(\mathbb{N}) directly implies both deletion optimality and truncation continuity, so Theorem 6 yields countable Pareto optimality together with equality of joint laws. To record your observation explicitly in the paper, we added it as a short corollary (Corollary 7, Sec. 6, lines 432–445; Supp. E.3, supp. lines 351–357).

  • Three-line deduction (lines 438–441): For exact FF on N\mathbb{N} with aF≥aGa_F \ge a_G: (1) aF(p,p−i)≥aG(p,p−i)=1−pia_F(p, p^{-i}) \ge a_G(p, p^{-i}) = 1 - p_i gives deletion optimality (eq. (4)); (2) for TNp=p∣{1,…,N}T_N p = p\vert_{\lbrace 1, \dots, N \rbrace}, P(F(TNp)≠F(p))=1−aF(p,TNp)≤1−∑k=1Npk→0\mathbb{P}(F(T_N p) \ne F(p)) = 1 - a_F(p, T_N p) \le 1 - \sum_{k=1}^N p_k \to 0 as N→∞N \to \infty gives truncation continuity; (3) Theorem 6 identifies the joint law of FF with GG. Corollary 7 thus extends Theorem IV.4 of Moulton & Jiang from finite to countable label sets and from equal agreements to equal joint laws (lines 443–445).
  • Corollary 7(a)–(b) (lines 432–436): Requiring aF≥aGa_F \ge a_G only on single-label deletion pairs (p,p−i)(p, p^{-i}) and finite-prefix truncation pairs (p,TNp)(p, T_N p) already forces Gumbel's joint law; equivalently, attaining aF(p,p∣S)=p(S)a_F(p, p\vert_S) = p(S) on all subset-restriction pairs characterizes Gumbel on N\mathbb{N}.
  • Why truncation pairs cannot be dropped (lines 446–458; Fig. 3b; Supp. E.4–E.5): On pk=2−kp_k = 2^{-k}, the exact, deletion-optimal tail-split sampler satisfies aF(p,TNp)→1/3<1a_F(p, T_N p) \to 1/3 < 1, losing on truncation pairs; the clock-refresh sampler shows that even among distributions sharing one fixed tail, deletion optimality alone does not determine the joint law.

Thank you again for a review that directly strengthened both the scholarship and clarity of the paper.

Reviewer_BBrjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies sampling algorithms FF. The main quantity they are interested in P[F(p)=F(q)]\mathbb{P}[F(p) = F(q)]; they want this to be as large as possible. Their main result states that the Gumbel sampler maximizes this quantity, and in fact it is the unique sampler with this property.

Critical strengths
  • The authors appear to present a substantial result, certifying the Pareto-optimality of the Gumbel sampler, with respect to the metric of aF(p,q):=P[F(p)=F(q)]a_F(p, q) := \mathbb{P}[F(p) = F(q)]. The metric aF(p,q)a_F(p, q) was previously considered by the previous work of Daliri, and they did ask in that work if the Gumbel sampler could be further improved. This work therefore resolves that open question. They prove an analog of this result for countable alphabets in Theorem 6.
Critical weaknesses
  • Despite the interest of their main result, I find that the paper is so confusingly written it should not be accepted in its current form. The main issue is that there are many terms and pieces of notation which are introduced without any definition. I compiled a list of some of these below. In addition, it is very hard to follow the logic of the arguments, partially due to the unexplained terminology, but also due to the way the arguments are presented. This makes it hard for me to be sure of the correctness of the arguments, or even the significance of some of their main results such as Theorem 4.

Some of the things that are not clearly defined:

  • The paper is about the Gumbel sampler but you don't even define it anywhere in the main text from what I can tell.
  • What is "binary nesting"? Why is it desirable?
  • What are the ei,eje_i, e_j in equation (7)?
  • What does "exact" mean in Lemma 3?
  • What does "menu" mean?
  • What does "face" mean?
  • What does "rational squeezing" mean?
  • What does i≻ji \succ j mean in equation (15)?
  • What does "Maximal Bernoulli coupling"
Questions for authors
  • Could you please explain the terminology that I flagged above? This way I will be able to validate the proof of your main theorem.
  • What is the significance of Theorem 4? In what way does it relate to your Theorem 1?
2 comments
AuthorsOpenReview ↗

Response to Reviewer BBrj (Part 1/2)

Response to Reviewer BBrj (Part 1/2)

Thank you for recognizing Theorems 1 and 6 as substantial results and listing each unclear term. We replaced coined shorthand with standard terminology, added explicit definitions in Section 2 (Defs. 1–3, lines 123–161) and Table 1 (lines 163–176), and structured Section 4 (lines 248–349) into five steps matching Section 1's roadmap (lines 104–115). Below are plain-language answers and main.pdf line numbers for [W1]–[W10]; Part 2/2 covers [Q1]–[Q2].

[W1] Many terms and symbols are introduced without definition, making it hard to verify the arguments or see the significance of results like Theorem 4.

Response: We define each flagged term and symbol explicitly (Defs. 1–3, lines 123–161; lines 262–306) and list notation in Table 1 (lines 163–176). Section 4 (lines 248–349) follows the roadmap (lines 104–115); Theorem 4 (lines 356–368) is Lemma 3's quantitative counterpart ([Q2], Part 2/2).

[W2] The Gumbel sampler is not defined in the main text.

Response: Shared Gumbel sampling draws independent standard Gumbels once as the seed and picks the label maximizing log-probability plus noise—equivalently, label ii's clock Ei/piE_i/p_i rings first (Def. 2, eq. (2), lines 133–145; Fig. 1a, lines 54–75; Table 1, line 169): G(p)=arg⁡max⁡i∈supp⁡p(log⁡pi+Γi)=arg⁡min⁡i∈supp⁡p(Ei/pi),Ei=e−Γi∼i.i.d.Exp(1).G(p) = \arg\max_{i \in \operatorname{supp} p} (\log p_i + \Gamma_i) = \arg\min_{i \in \operatorname{supp} p} (E_i / p_i), \qquad E_i = e^{-\Gamma_i} \overset{\text{i.i.d.}}{\sim} \mathrm{Exp}(1).

[W3] What is "binary nesting", and why is it desirable?

Response: It meant monotone two-label comparisons: on {i,j}\lbrace i, j \rbrace, picking ii at odds rr implies picking ii at s>rs > r (Cij(r)≤Cij(s)C_{ij}(r) \le C_{ij}(s) a.s.; Step 3, lines 298–299; Table 1, line 175). Any reversal Rev={Cij(r)=1,Cij(s)=0}\mathrm{Rev} = \lbrace C_{ij}(r)=1, C_{ij}(s)=0 \rbrace loses agreement (aG−aF=2P(Rev)a_G - a_F = 2 \mathbb{P}(\mathrm{Rev}) on (Pij(r),Pij(s))(P_{ij}(r), P_{ij}(s)), eq. (9), lines 300–306), so monotonicity equals attaining 1−dTV1 - d_{\mathrm{TV}} on two-label pairs.

[W4] What are the symbols in equation (7)?

Response: Submitted Eq. (7) is Eq. (8) (lines 262–265; Table 1, lines 172–173): ei\mathbf e_i (formerly eie_i) is the point mass at ii, Pij(x)=(xei+ej)/(1+x)P_{ij}(x) = (x \mathbf e_i + \mathbf e_j)/(1+x) gives ii odds xx vs. jj, 1{⋅}\mathbf 1\lbrace \cdot \rbrace is the indicator, and Cij(x)=1{F(Pij(x))=i}C_{ij}(x) = \mathbf 1\lbrace F(P_{ij}(x)) = i \rbrace indicates FF picking ii (P(Cij(x)=1)=x1+x\mathbb{P}(C_{ij}(x)=1) = \frac{x}{1+x}).

[W5] What does "exact" mean in Lemma 3?

Response: FF is exact if P(F(p)=i)=pi\mathbb{P}(F(p) = i) = p_i for all p,ip, i (Def. 1, eq. (1), lines 123–126; Table 1, line 166). Lemma 3 (lines 308–314, eq. (10); line 250) assumes FF is exact with zero deletion deficits δ(qt)=δ(qt′)=0\delta(q_t) = \delta(q_t') = 0 on the 2m2m chain inputs.

[W6 & W7] What did "menu" and "face" mean?

Response: "Menu" meant an input distribution p∈Δ(A)p \in \Delta(A) (lines 119–124), and "face" meant a two-label restriction p∣Sp\vert_S such as q−k=Pij(qi/qj)q^{-k} = P_{ij}(q_i / q_j) (Def. 3, lines 146–149; lines 266–267; Table 1, line 165). Both coined terms are replaced by these standard names.

[W8] What does "rational squeezing" mean?

Response: It is the standard sandwiching step identifying Cij(x)C_{ij}(x) at real odds xx with 1{Rij≤x}\mathbf 1\lbrace R_{ij} \le x \rbrace via rationals x−<x<x+x^- < x < x^+ (Step 4, lines 324–328; Supp. A.2, supp. lines 54–64): on the probability-one event covering rationals, Rij=inf⁡{r∈Q>0:Cij(r)=1}R_{ij} = \inf\lbrace r \in \mathbb Q_{>0} : C_{ij}(r) = 1 \rbrace has CDF x1+x\frac{x}{1+x}, and Cij(x−)≤Cij(x)≤Cij(x+)C_{ij}(x^-) \le C_{ij}(x) \le C_{ij}(x^+) gives Cij(x)=1{Rij≤x}C_{ij}(x) = \mathbf 1\lbrace R_{ij} \le x \rbrace a.s.

[W9 & W10] What does the symbol in equation (15) mean, and what is a "maximal Bernoulli coupling"?

Response: The revision writes this uniformly as Πq\Pi_q, the 3-label ranking i≻j≻ki \succ j \succ k on a three-label input qq (Step 2, lines 268–269, 287–288; Table 1, line 174): F(q)F(q) ranks first and FF orders the rest on their two-label restriction, giving P(Πq=i≻j≻k)=qiqj1−qi\mathbb{P}(\Pi_q = i \succ j \succ k) = \frac{q_i q_j}{1 - q_i} (Lemma 2, lines 289–294). "Maximal Bernoulli coupling" is now a maximal coupling of two-label distributions—attaining 1−dTV1 - d_{\mathrm{TV}}, which Gumbel attains via Cij(x)=1{Ei/Ej<x}C_{ij}(x) = \mathbf 1\lbrace E_i / E_j < x \rbrace (Step 3, lines 300–306; lines 207–208; Supp. A.4, supp. lines 92–100).

AuthorsOpenReview ↗

Response to Reviewer BBrj (Part 2/2)

Response to Reviewer BBrj (Part 2/2)

For [Q1], Section 4 (lines 248–349) now proves Theorem 1 in five short, self-contained steps directly from Definitions 1–3, with countable-rational null-set bookkeeping written out in Supp. A (supp. lines 32–88). For [Q2], Theorem 4 (lines 356–368) is the quantitative stability version of Step 3 (Lemma 3): practical samplers using finite precision or hashed seeds are only approximately deletion-optimal, and Theorem 4 bounds their agreement loss on an untested two-label pair directly from deletion tests on finitely many three-label inputs.

[Q1] With the terminology clarified, how can the proof of Theorem 1 be validated step by step?

Response: Section 4 (lines 248–349) separates the proof of Theorem 1 into five self-contained steps matching the roadmap in Section 1 (lines 104–115), with countable-rational null-set bookkeeping in Supp. A (supp. lines 32–88):

StepClaimMechanism & location in Section 4
1Deleting an unsampled label keeps the output unchangedDeficit identity di(p)=P(F(p)≠i,F(p−i)≠F(p))=0d_i(p) = \mathbb{P}(F(p) \ne i, F(p^{-i}) \ne F(p)) = 0 (Lemma 1, lines 253–260)
2Pairwise choices on any 3-label input are transitiveWinner survives both deletions, inducing ranking Πq\Pi_q (Step 2 & Lemma 2, lines 262–269, 287–296)
3Two-label choices are monotone in the odds x=pi/pjx = p_i / p_jChain of 2m2m three-label inputs forces P(Rev)≤2/(1+λm/2)→0\mathbb{P}(\mathrm{Rev}) \le 2/(1 + \lambda^{m/2}) \to 0 (Lemma 3, eq. (10), Fig. 2, lines 270–285, 298–323)
4Thresholds factor as ratios of input-free clocksRik=RijRjkR_{ik} = R_{ij} R_{jk} a.s.; setting τ1=1,τi=Ri1\tau_1 = 1, \tau_i = R_{i1} gives F(p)=arg⁡min⁡i(τi/pi)F(p) = \arg\min_i (\tau_i / p_i) (Step 4, eq. (11), lines 324–339; Supp. A.3)
5Exact marginals identify Gumbel's exponential-ratio lawExactness gives (τ1/τn,…,τn−1/τn)(\tau_1/\tau_n, \dots, \tau_{n-1}/\tau_n) the joint survival function of (E1/En,…,En−1/En)(E_1/E_n, \dots, E_{n-1}/E_n) (eq. (12), lines 340–349)

Step 3 is proved in seven lines in Lemma 3 (lines 308–321) and illustrated in Figure 2 (lines 270–285): chaining transitivity across 2m2m three-label inputs that share two-label restrictions confines any reversal Rev={Cij(r)=1,Cij(s)=0}\mathrm{Rev} = \lbrace C_{ij}(r)=1, C_{ij}(s)=0 \rbrace (r<sr < s, λ=s/r\lambda = s/r) to an endpoint union of probability at most 2/(1+λm/2)→02/(1 + \lambda^{m/2}) \to 0 as m→∞m \to \infty, without assuming continuity of FF in its input.

[Q2] What is the significance of Theorem 4, and how does it relate to Theorem 1?

Response: Theorem 4 is the quantitative stability version of Lemma 3 (Step 3 of Theorem 1): it certifies an upper bound on how much agreement an exact sampler loses on an untested target two-label pair using only deletion deficits measured on 2m2m explicit three-label inputs (Sec. 5, Theorem 4, eqs. (13)–(15), lines 351–377 and 403–411; Fig. 3a, lines 378–400).

For any exact sampler FF, its agreement loss on (Pij(r),Pij(s))(P_{ij}(r), P_{ij}(s)) satisfies (UmU_m explicit in eq. (14), line 362) 12[aG(Pij(r),Pij(s))−aF(Pij(r),Pij(s))]=P(Rev)≤Um(y)+∑t<m(δ(qt)+δ(qt′)).\tfrac{1}{2}\bigl[a_G(P_{ij}(r), P_{ij}(s)) - a_F(P_{ij}(r), P_{ij}(s))\bigr] = \mathbb{P}(\mathrm{Rev}) \le U_m(y) + \sum_{t < m} \bigl(\delta(q_t) + \delta(q_t')\bigr).

  • Link to Theorem 1 and finite testing: When all deletion deficits are zero, letting m→∞m \to \infty in Eq. (13) recovers monotonicity (Lemma 3), the step on which Theorem 1 rests (lines 372–373). When every tested deficit on the 2m2m chain inputs is at most ε>0\varepsilon > 0, choosing m=⌈3log⁡(1/ε)/(2log⁡λ)⌉m = \lceil 3 \log(1/\varepsilon) / (2 \log \lambda) \rceil certifies an agreement loss of O(εlog⁡(1/ε))O(\varepsilon \log(1/\varepsilon)) on the untested pair (eq. (15), lines 364–377), and Figure 3a (lines 378–400, 408–410) shows this certificate tracking the true loss linearly across departure scales.
  • Extension to general finite targets: Proposition 5 (already in the submission; revised lines 413–419; Supp. D, supp. lines 311–323) shows by compactness that finite deletion certificates also exist for any finite family of rational target distributions within total-variation tolerance η\eta.

Thank you again for your detailed questions, which helped us sharpen the definitions, notation table, and five-step proof presentation.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all three reviewers for their careful reading, constructive feedback, and pointers to prior literature, and have uploaded the revised main.pdf and supp.pdf (Supp./S denote the supplement). Our main result is that on a finite set of at least three labels, shared Gumbel sampling is the only exact shared-seed rule (up to equality of joint output distributions) under which deleting an unsampled label never changes the output (Theorem 1, lines 181–190), while on countable label sets adding consistency under prefix truncation restores uniqueness (Theorem 6, lines 428–429). In the revision, we rewrote the Abstract, Introduction, setup, and five-step proof in standard terminology with a notation table (Reviewers BBrj, Pn9v), credited Moulton & Jiang (2018) for finite pairwise Pareto optimality and weighted-MinHash domination while clarifying how our results complement theirs (Reviewer sGmB), and highlighted Theorem 4 as the quantitative stability version of the proof's monotonicity step (Reviewer BBrj).

1. Main result

Shared-seed categorical sampling maps a distribution pp and shared seed ω\omega to a label F(p,ω)F(p, \omega) with exact marginals P(F(p)=i)=pi\mathbb{P}(F(p) = i) = p_i (Def. 1, eq. (1), lines 123–126); p−ip^{-i} denotes pp after deleting label ii and renormalizing (Def. 3, lines 148–149). Under shared Gumbel sampling (Def. 2, eq. (2), lines 133–137), G(p)=arg⁡max⁡i(log⁡pi+Γi)=arg⁡min⁡i(Ei/pi),Ei∼i.i.d.Exp(1),G(p) = \arg\max_i (\log p_i + \Gamma_i) = \arg\min_i (E_i / p_i), \qquad E_i \overset{\text{i.i.d.}}{\sim} \mathrm{Exp}(1), deleting an unsampled label keeps the winner unchanged, attaining the total-variation ceiling 1−pi1 - p_i (eq. (4), line 151). Theorem 1 (lines 181–190) proves the converse: on n≥3n \ge 3 labels, an exact sampler attains agreement 1−pi1 - p_i on every deletion pair (p,p−i)(p, p^{-i}) iff it has GG's joint law across all finite input lists. Exact marginals alone admit infinitely many non-Gumbel joint laws (shared-uniform inverse-CDF, weighted MinHash, hierarchical P-MinHash), all falling below 1−pi1 - p_i on deletion pairs (Fig. 1b, lines 54–75); uniqueness also fails for n=2n = 2 (lines 198–200) and on N\mathbb{N} without truncation continuity (Sec. 6, lines 446–458).

2. Summary of revisions

The submission's results (Theorems 1, 4, and 6, Corollary 2, Lemma 3, and Proposition 5) are unchanged in substance; besides formatting inline definitions and identities as Definitions 1–3 and Lemmas 1–2, the only new results are two short statements (Proposition 3 and Corollary 7) added directly to answer Reviewer sGmB's questions.

Reviewer pointRevisionLocation
Notation & exposition (BBrj, Pn9v)Rewrote Abstract/Intro; defined flagged terms & symbols (Defs. 1–3, Table 1); 5-step roadmap & prooflines 11–31, 34–115, 123–176, 248–349
Moulton & Jiang (2018) (sGmB)Credited M&J for finite pairwise Pareto optimality (Thm IV.4) and dominating weighted MinHash (Thm IV.5)line 24; lines 82–102, 208–214, 466; Supp. B.3
Where FF loses vs. GG (sGmB)Added brief Prop. 3 to answer sGmB [W3], complementing M&J Thm IV.4 via M&J's bridge zℓz^\elllines 215–246; Supp. B
Countable Pareto (sGmB)Added brief Cor. 7, as Reviewer sGmB observed, deducing countable Pareto optimality & equal joint laws from Thm 6lines 432–445; Fig. 3b; Supp. E.3
Significance of Thm 4 (BBrj)Presented Thm 4 as the quantitative stability version of Lemma 3 (alongside submitted Prop. 5 for rational targets)lines 351–419; Fig. 3a; Supp. C–D

Standardized replacements for coined terms: menu →\to input distribution pp (lines 119–124); face →\to two-label restriction p∣Sp\vert_S (lines 146–149, 266–267); binary nesting →\to monotone two-label comparisons (lines 298–306); race representation →\to random-utility form arg⁡min⁡iτi/pi\arg\min_i \tau_i / p_i (eq. (11), lines 335–338).

  • Null sets & applications: Sec. 4 (lines 248–349) and Supp. A (supp. lines 32–88) write out the countable-rational null-set bookkeeping. For drafter-invariant speculative decoding and keyed LLM watermarking (lines 36–51, 77–80), Cor. 2(a) shows any non-Gumbel exact rule loses agreement on some single-token ban, and Thm 4 bounds target-pair loss from finite deletion tests.

Thank you again to all three reviewers for feedback that strengthened the paper.

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

Related papers

Discussion (0)

Sign in to comment.