{"id":"554ff745-ea02-4b01-b4d9-84498c93a22f","arxiv_id":"2607.11146","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Rank-conditioned Horvitz–Thompson reuses all C(n,K) subsets of one Gumbel-Top-n pool for unbiased Plackett–Luce best-of-K value and score-function gradient, with an exact Max-specific DP collapse to a 1-D integral.","lead":"This paper builds an unbiased sample-reuse estimator for best-of-K reward when candidates are drawn without replacement via Plackett–Luce / Gumbel-Top-K, the law of Stochastic Beam Search. It matters because existing Max@K gradient estimators assume i.i.d. draws and are provably biased under the coupled sampler used in practice for tours and LLM generations.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the finite full-support, M≥n+1, \theta-independent bounded rewards, and continuous differentiability assumptions that license the exponential-race conditioning and the integrable dominating envelope. Those assumptions are explicit, the proofs (Theorem 1, Propositions 1–2, Appendices A–B) track them carefully, and the numerical certificates plus ancillary suite give independent support. The open quadrature-rate and infinite-support items are already labeled as open; they do not falsify the finite-support claims. No internal inconsistency or unstated load-bearing gap appears that would move the verdict away from ACCEPT. The concrete test simply reconfirms the already-shipped certificates under an independent re-implementation of the two novel algorithmic pieces.","tokens_in":27329,"tokens_out":504,"duration_ms":5701,"concrete_test":"Re-run the fine-grid deterministic Gauss–Legendre certificate of §6 (M=5, n=3, K∈{2,3}, declared logits/rewards) after independently re-implementing only the pool-only sampler log-density of Corollary 1 and the reward-sorted DP of Theorem 2 from the exponential-race identities; confirm that value error, gradient relative L2, and sampler-mass residual remain below 10^{-11} and that poly-vs-brute residuals stay machine-precision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central finite-support claims (unbiasedness of the rank-conditioned HT estimator for J_K^WOR, unbiased score-function surrogate gradient, exact combinatorial collapse of the subset sum to a 1-D integral, and n≥2K second-moment sufficiency for both objective terms and the full gradient) are proved under the stated assumptions, numerically certified against exact enumeration, and accompanied by runnable ancillary tests. The weakest points the authors themselves flag—no certified finite-Q quadrature rate, open gradient-level sharpness for n<2K, and open countably-infinite support—are domain restrictions or deferred items rather than hidden gaps that undermine the theorems as stated. The practical public loss is explicitly an approximation to the ideal surrogate; the paper never claims algebraic exactness or an ε-rate for fixed Q.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the coupled best-of-K objective J_K^WOR under Plackett–Luce / Gumbel-Top-K sampling without replacement, which is distinct from the i.i.d. Max@K objective targeted by PKPO, RSPO, MaxPO and related estimators. It shows that reusing those i.i.d. weights under the coupled sampler is biased (closed-form three-item instance with E[g_iid] = (4/5) \nabla J_K^WOR). The contribution is a rank-conditioned Horvitz–Thompson estimator (⋆) that reuses all C(n,K) K-subsets of one Gumbel-Top-n pool and its observed priority threshold: Theorem 1 proves unbiasedness for J_K^WOR, Proposition 1 an unbiased score-function surrogate gradient, and Theorem 2 an exact reward-sorted DP collapse of the combinatorial subset sum to a one-dimensional integral evaluable by fixed-Q Gauss–Laguerre quadrature in O(n log n + n K Q). Remark 1 and Proposition 2 establish that each nonzero degree-K HT term and the full surrogate gradient have finite second moment whenever n ≥ 2K. At K=1 the construction recovers classical priority sampling; Corollaries 1–2 cover finite structured sequence policies under exact SBS. Finite-model certificates against exact enumeration and ancillary validation code are provided; a certified finite-Q error bound and countably infinite support remain open.","tokens_in":27495,"tokens_out":1336,"duration_ms":13131,"significance":"If the results hold, the paper supplies the first sample-reuse (n>K) unbiased estimator and gradient for the genuine sampler-level WOR Max@K objective realized by Gumbel-Top-K / Stochastic Beam Search. That fills an explicit gap left open by the i.i.d. Max@K literature (MaxPO’s “correlated generations” limitation) and by generic joint-score REINFORCE, which is already unbiased but does not reuse a larger pool. Strengths that raise the contribution above a routine application of HT include: (i) the closed-form three-item bias certificate, (ii) the Max-specific O(nK)-per-node collapse that removes the C(n,K)·K! cost, (iii) the n≥2K second-moment regime for the full gradient (not only the objective terms), (iv) pool-only computability that covers exact SBS sequence policies without support enumeration, and (v) machine-checked finite-model certificates (residuals <10^{-11}) plus runnable ancillary tests. The work is a theory-and-certification note rather than an application benchmark; its practical value is therefore conditional on the deferred NCO/LLM experiments, but the technical core is self-contained and carefully scoped.","major_comments":[{"comment":"The public training loss is the fixed-Q quadrature approximation ˆJ_Q of the ideal integral (Theorem 2, Algorithm 1). The paper correctly states that no ε-approximation rate for value or gradient is certified and that a uniform finite-Q bound remains open (§8). Because the central claims of unbiasedness (Theorem 1, Proposition 1) and second-moment control (Proposition 2) are proved only for the ideal ˆJ, the manuscript should make the ideal-vs-public distinction even more prominent in the abstract and introduction: the theorems certify the ideal surrogate; the shipped loss is a numerical approximation whose error is only checked on the finite configurations of §6. This is already acknowledged, but a short explicit “what is proved vs. what is shipped” paragraph would prevent over-reading of the practical recipe.","section":null},{"comment":"Proposition 2 establishes sufficiency of n≥2K for finite second moment of the full surrogate gradient; sharpness (whether the aggregated gradient can remain square-integrable for n<2K via cross-term cancellation) is left open. Remark 1 already shows term-level divergence for n<2K. For a theory note this is acceptable, but the training-stability claim in the abstract and introduction should be phrased strictly as “sufficient when n≥2K,” not as a sharp operating regime, until the open direction is settled or a counter-example is exhibited.","section":null}],"minor_comments":[{"comment":"Observation 2’s closed-form instance (M=3, K=n=2, R=(1,0,0)) is excellent; a one-line pointer in the abstract to the exact factor 4/5 would help readers locate the bias certificate immediately.","section":null},{"comment":"Table 1 reports wall-clock medians on a single Apple M4 core; a brief note that the numbers are hardware-dependent (already present) is fine, but adding the corresponding flop count or asymptotic comparison would make the 650\times claim more portable.","section":null},{"comment":"Appendix E / Figure 1 is correctly labelled “illustrative” and not a decision rule; the main text (§3, §8) already cautions against over-generalization. Consider moving the figure into the main body only if space permits, otherwise the current placement is appropriate.","section":null},{"comment":"Notation: the three “i.i.d.-weight” objects (iid-grad, iid-SubLOO, shared-value score) are carefully distinguished in §3; a short glossary table would further reduce the risk of conflation by readers coming from the PKPO/RSPO literature.","section":null},{"comment":"Typographical: “raison d’être” appears with a circumflex encoding artifact in §8; fix to “raison d’être” or “raison d'etre.”","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is unusually careful about scope, open problems, and ideal-vs-public distinctions; the ancillary test suite is a genuine asset. Fit for a theory-oriented ML journal is good. The deferred multi-seed NCO benchmark is correctly left out of this note; I would not require it for acceptance of the present theory-and-certification contribution."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the missing unbiased sample-reuse gradient for the sampler people actually run (Gumbel-Top-K / SBS), not the i.i.d. Max@K objective the recent PKPO/RSPO/MaxPO line targets. The three-item closed form showing the i.i.d. weights give exactly 4/5 of the true gradient is clean and settles the bias claim without hand-waving.\n\nWhat is new is the degree-K instantiation: rank-conditioned HT on the Plackett–Luce best-of-K set total, plus a reward-sorted DP that collapses the C(n,K) subset sum (each carrying a K!-cost set probability) exactly to a 1-D integral. Fixed-Q evaluation is O(n log n + n K Q). They recover classical priority sampling at K=1 and PKPO’s weight profile (up to scalar) in the uniform limit. Finite second-moment of the HT terms and of the full surrogate gradient when n ≥ 2K is proved; gradient-level sharpness for n < 2K is left open. Pool-only forms cover exact SBS on finite structured sequences without enumerating the support.\n\nThe math is careful. Unbiasedness, gradient unbiasedness, and the combinatorial collapse have full appendices; finite-model certificates against enumeration hit 1e-11; poly-vs-brute matches to machine precision; ancillary tests pin the κ-detach convention and the score bounds. They do not claim an ε-rate for fixed-Q quadrature or algebraic exactness of the public loss, and they flag infinite support as open. That honesty is useful.\n\nSoft spots are real but proportionate: no certified quadrature error bound, no application benchmark (explicitly deferred), and the practical loss is a numerical approximation to the ideal surrogate. None of those undermine the theorems as stated. Citation pattern is accurate; they credit Duffield, Cohen–Kaplan, and Kool rather than over-claiming the conditioning device.\n\nThis is for people who care about policy gradients under genuine sampler-level coupling (NCO, some LLM pass@K setups). A serious editor should send it to referees. I would cite the estimator and the n ≥ 2K condition, and I would bring it to reading group.","headline":"Solid theory note that actually fills the WOR Max@K sample-reuse gap with proved unbiasedness, an exact DP collapse, and shipped certificates; open items are labeled, not hidden.","tokens_in":28157,"tokens_out":560,"would_cite":true,"duration_ms":6850,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"From one Gumbel-Top-n pool you can reuse every size-K subset for an unbiased gradient of the without-replacement best-of-K objective.","keywords":["Plackett-Luce","best-of-K","without replacement","Horvitz-Thompson","Gumbel-Top-n","Stochastic Beam Search","policy gradient","sample reuse"],"falsifier":"On any finite enumerable support with M greater than or equal to n+1, replace the Monte-Carlo expectation of the estimator and its surrogate gradient by deterministic quadrature over the priority threshold and check whether both equal the exact enumerated objective and gradient to machine precision; a systematic mismatch falsifies the unbiasedness claims.","tokens_in":28185,"feed_emoji":"🎯","tokens_out":733,"duration_ms":7537,"temperature":0.7,"pith_summary":"When a system draws K distinct candidates without replacement (as Stochastic Beam Search or Gumbel-Top-K does) and keeps the best, the quantity being optimized is different from the ordinary i.i.d. best-of-K. Existing sample-reuse gradient estimators that assume independent draws become biased under this coupling; a three-item closed form shows the bias can be exactly 20 percent. The paper supplies the missing without-replacement counterpart: condition on the observed priority threshold of a larger Gumbel-Top-n pool, reweight every embedded K-subset by its Horvitz–Thompson inclusion probability, and thereby obtain an unbiased estimator of the coupled objective together with an unbiased score-function policy gradient. A reward-sorted dynamic program then collapses the combinatorial subset sum into a single one-dimensional integral that fixed-node quadrature evaluates in linearithmic time. The construction needs only the probabilities of the drawn items, so it applies to finite structured sequence policies decoded by exact Stochastic Beam Search, and it recovers classical priority sampling when K equals one.","feed_headline":"One Gumbel pool reuses every K-subset for unbiased WOR Max@K","feed_subtitle":"Rank-conditioned weights fix the bias of i.i.d. Max@K estimators under coupled sampling","key_machinery":"The rank-conditioned Horvitz–Thompson estimator (⋆): condition on the observed (n+1)-st priority, reweight every size-K subset of the pool by the product of its conditional inclusion probabilities, then evaluate the resulting subset total via a reward-sorted elementary-symmetric dynamic program that reduces it to a single integral.","core_discovery":"A rank-conditioned Horvitz–Thompson estimator built from one Gumbel-Top-n pool and its observed priority threshold is unbiased for the Plackett–Luce without-replacement best-of-K objective and yields an unbiased exact score-function surrogate gradient; a Max-specific dynamic program collapses the subset sum exactly to a one-dimensional integral evaluable by fixed-Q quadrature in O(n log n + n K Q) arithmetic, with finite second moment of every nonzero degree-K term and of the full gradient whenever n is at least twice K.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["One Gumbel-Top-n pool yields unbiased WOR Max@K via rank-conditioned HT","Rank-conditioned weights reuse every K-subset from a single Gumbel pool","Horvitz-Thompson on Gumbel pool gives unbiased PL without-replacement Max@K","Priority-threshold HT collapses C(n,K) subsets to a 1D integral for WOR Max@K","Unbiased surrogate gradient for coupled best-of-K from one Gumbel-Top-n draw"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The policy must put positive probability on every item of a fixed finite support large enough to leave at least one item outside the pool, and the rewards must not depend on the policy parameters.","fun_headline_variants_meta":{"raw":{"variants":["One Gumbel-Top-n pool yields unbiased WOR Max@K via rank-conditioned HT","Rank-conditioned weights reuse every K-subset from a single Gumbel pool","Horvitz-Thompson on Gumbel pool gives unbiased PL without-replacement Max@K","Priority-threshold HT collapses C(n,K) subsets to a 1D integral for WOR Max@K","Unbiased surrogate gradient for coupled best-of-K from one Gumbel-Top-n draw"]},"model":"grok-4.5","effort":"low","cost_usd":0.007062,"raw_usage":{"total_tokens":1935,"prompt_tokens":1041,"num_sources_used":0,"completion_tokens":127,"cost_in_usd_ticks":70620000,"prompt_tokens_details":{"text_tokens":1041,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":767,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1041,"tokens_out":127,"duration_ms":8219,"temperature":1.0,"reasoning_tokens":767,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T06:43:20.881173+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On any finite enumerable support with M greater than or equal to n+1, replace the Monte-Carlo expectation of the estimator and its surrogate gradient by deterministic quadrature over the priority threshold and check whether both equal the exact enumerated objective and gradient to machine precision; a systematic mismatch falsifies the unbiasedness claims.","supporting_citations":[],"review_version":1}