{"id":"a6a5ae67-a9ce-4fe8-af14-41b4ef1e76d1","arxiv_id":"2505.03156","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Soft Best-of-n sampling provably approaches the optimal tilted reward distribution at O(1/n) KL divergence and relative reward error, with sample complexity that grows exponentially in sequence length for blockwise sampling.","lead":"The paper introduces Soft Best-of-n sampling, a variant of Best-of-n that selects among n generated responses using a softmax over their rewards, with a temperature parameter controlling the tradeoff between reward and distribution shift. It proves finite-sample convergence rates to the optimal tilted distribution and analyzes why whole-sequence Best-of-n becomes inefficient for long outputs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's TV lower bound is false: in the paper's own binary example, TV decays as O(1/n), not Ω(1/√n), so the 'sharp' O(1/n) claim and the blockwise 'fundamental limitation' are not established.","rationale":"Read in good faith: the core upper bound (Theorem 1) is correct; the proof via Lemma 1 and Jensen is clean, and the binary example confirms the O(1/n) KL rate. The load-bearing weakness is Theorem 2, which is used to claim the rate cannot be improved and to justify the 'fundamental limitations' of blockwise sampling (Section IV.C, eq. 18). The proof is not merely incomplete; the claimed TV lower bound is false. In the binary example of Appendix D, Pn,λ(1) = n p e^{1/λ} E[(e^{1/λ}+S_{n-1})^{-1}], and the delta-method expansion shows TV = Θ(1/n), not Ω(1/√n). Therefore (8) fails for any fixed C'>0 once n is large. The Berry-Esseen proof produces a spurious O(1/√n) gap because it sets δ = O(1/√n), making the Gaussian tail factor constant and the tail integral O(1/√n), whereas the actual centered fluctuations contribute only O(1/n). Since Theorem 2 underpins the 'sharp' and 'cannot be improved' claims, those central claims are unsupported as stated. The blockwise i.i.d./additive limitation is acknowledged by the authors and is a modeling caveat, not an internal contradiction; the false lower bound is an internal contradiction with the paper's own example. Verdict: reject the current version, since a central theorem is false; the paper can be rehabilitated by removing/correcting Theorem 2 and qualifying the sharpness claims, while keeping Theorem 1.","tokens_in":21662,"tokens_out":17112,"duration_ms":143925,"concrete_test":"Analytically compute TV for the binary example of Appendix D: derive Pn,λ(1) = n p e^{1/λ} E[(e^{1/λ}+S_{n-1})^{-1}], expand the expectation to second order in (n-1)^{-1/2}, and show TV = c/n + O(n^{-2}) with c = p(1-p)e^{1/λ}(e^{1/λ}-1)/(p e^{1/λ}+1-p)^3. Then verify that for n > (c/C')^2, the inequality TV ≥ C'/√(n-1) of Theorem 2 is violated for every fixed C'>0. Alternatively, run a high-precision Monte Carlo of the Soft Best-of-n selection for n=10^4,10^6,10^8 and confirm the TV values fall below C'/√(n-1).","verdict_should_be":"REJECT","load_bearing_attack":"Appendix E's proof of Theorem 2 tries to show TV(P*_λ,P_{n,λ}) ≥ C'/√(n-1) via Berry-Esseen. But the argument is invalid and the claimed bound contradicts the paper's own binary example (Appendix D). For X={0,1}, P(1)=p, r(x)=1_{x=1}, the exact Pn,λ(1) = n p e^{1/λ} E[1/(e^{1/λ}+S_{n-1})] with S_{n-1}=(n-1)+K(e^{1/λ}-1), K~Bin(n-1,p). Expanding for large n gives TV = |P*_λ(1)-Pn,λ(1)| = p(1-p)e^{1/λ}(e^{1/λ}-1)/(n(p e^{1/λ}+1-p)^3) + O(n^{-2}) = O(1/n). Hence for any fixed C'>0, TV < C'/√(n-1) for all sufficiently large n, so (8) fails. The flaw in the proof: the average S_{n-1} has fluctuations of order 1/√n, but they are centered, so the expectation of 1/(c+S) differs from 1/(c+1) at order 1/n; the crude tail bound used with δ=O(1/√n) produces a spurious O(1/√n) gap. Consequently, the claimed Θ(1/n) rate in KL is not proven by this route, and the statements that the O(1/n) rate 'cannot be improved' and that the blockwise sample-complexity condition (18) 'cannot be improved in general due to our lower bound' are unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Soft Best-of-n sampling, a temperature-parameterized generalization of Best-of-n in which the selected index is drawn according to softmax weights e^{r(X_i)/λ}. The main theoretical claim is that the induced distribution P_{n,λ} converges to the tilted optimal distribution P*_λ at rate O(1/n) in KL divergence, with explicit constants (Theorem 1), that this rate cannot be improved in general (Theorem 2), that the expected reward gap also shrinks as O(1/n) (Theorem 3), and that for an additive reward model over length-m blocks, blockwise sampling requires exponentially many samples in m (Theorem 4, Corollary 2, and equation (18)). The paper also positions the method as a way to interpolate smoothly between the base distribution and the reward-maximizing distribution, thereby spanning the KL-reward Pareto frontier.","tokens_in":21970,"tokens_out":6467,"duration_ms":63802,"significance":"If the upper-bound results stand, this is a useful theoretical contribution to inference-time alignment. Theorem 1 is clean, self-contained, and gives explicit constants; Theorem 3 provides a similarly clean reward-gap bound. The binary example in Appendix D is a nice explicit calculation that matches the O(1/n) leading constant of the upper bound. The blockwise additive-reward model is a sensible minimal setting for exposing a real trade-off between symbolwise and blockwise sampling. However, the claimed converse result (Theorem 2) is not merely missing a detail: it is contradicted by the paper's own binary expansion, which gives TV(P*_λ,P_{n,λ}) = O(1/n). The subsequent statements that the O(1/n) rate 'cannot be improved' and that the blockwise sample-complexity condition is optimal are therefore unsupported. The central constructive results are publishable, but the sharpness and 'fundamental limitation' claims require substantial correction.","major_comments":[{"comment":"Theorem 2, as stated, is false. In the binary example of Appendix D, the displayed expansion gives P_{n,λ}(1) = n p e^{1/λ}/(e^{1/λ} + (n-1)(p e^{1/λ} + 1 - p)) + O(1/n^2), so TV(P*_λ,P_{n,λ}) = |P*_λ(1) - P_{n,λ}(1)| = O(1/n). Consequently, for any fixed C' > 0, inequality (8) fails for all sufficiently large n. The Berry-Esseen argument in Appendix E cannot produce the claimed Ω(1/√n) gap: the fluctuation S_{n-1} - 1 is centered, so E[1/(c + S_{n-1})] differs from the mean-substituted value at order 1/n, whereas the proof's choice δ = O(1/√n) followed by a Gaussian tail bound creates a spurious O(1/√n) term. The proof also selects δ = 4C'/√(n-1) while stating only that this is valid for large n, and the appendix contains the sentence 'We will take care of it later' in the middle of the residual estimate. The claims following Theorem 2, including the statement that the O(1/n) rate 'cannot be improved' and the assertion in Section IV.C that condition (18) 'cannot be improved in general due to our lower bound', are therefore unsupported.","section":"Section III, Theorem 2 and Appendix E"},{"comment":"The sufficient condition in Corollary 2 is mis-stated. The proof of Corollary 2 derives λ ≥ 2/(m log(1 + 4(n(e^ϵ - 1))^{1/m})), but the theorem statement says λ ≥ 2/log(1 + 4(nϵ)^{1/m}), omitting both the 1/m factor and replacing e^ϵ - 1 with ϵ. The same error propagates into equation (18): the manuscript writes λ' = λm ≥ 2/log(1 + 4(nϵ)^{1/m}) and concludes n ≥ (1/ϵ)((e^{2/λ'} - 1)/4)^m. Correcting the derivation gives λ' ≥ 2m/log(1 + 4(n(e^ϵ - 1))^{1/m}) and n ≥ (1/(e^ϵ - 1))((e^{2m/λ'} - 1)/4)^m. The qualitative exponential dependence on m survives this correction, but the displayed condition and constants in (18) are not established as written. In addition, Theorem 2, even if repaired, would not by itself prove necessity of (18); no matching lower bound for the blockwise Soft Best-of-n setting is provided.","section":"Section IV.C, Corollary 2 and equation (18)"}],"minor_comments":[{"comment":"The sentence 'We will take care of it later' follows the claim that the cubic remainder is O(1/n^2); this residual estimate is load-bearing for the binary expansion and should be proved before publication.","section":"Appendix D"},{"comment":"Theorem 3 requires a non-degeneracy assumption such as E_{P*_λ}[r_λ(X)] > 0; otherwise the relative reward gap is undefined (e.g., when r is identically zero). Please add this assumption explicitly.","section":"Theorem 3"},{"comment":"Theorem 2 states a bound 'for integer n ≥ 1', but the proof is explicitly asymptotic and assumes finite third moments and support conditions; the statement should be rephrased as a large-n statement with the required non-degeneracy conditions stated.","section":"Theorem 2"},{"comment":"The displayed statement of Theorem 4 is hard to parse: the exponent '^m' appears to apply to the entire CV-based factor, but the bracketing and the notation '−1!^m' are unclear. Rewrite the bound as D_KL(P^{*m}_λ ∥ P^m_{n,λ}) ≤ log(1 + (1/n) CV(e^{r(X)/(mλ)})^{2m}).","section":"Theorem 4"},{"comment":"There is a typo in equation (25): 'DDKL' should be 'D_KL'.","section":"Appendix E"},{"comment":"The caption says 'optional KL-reward Pareto frontier' but should say 'optimal KL-reward Pareto frontier'.","section":"Figure 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper's core upper bounds (Theorems 1 and 3) are sound and valuable, but the converse Theorem 2 is contradicted by the paper's own Appendix D and cannot be repaired by minor edits to the proof. I would not reject: the authors can remove or weaken the lower-bound claims, correct the blockwise sample-complexity calculations, and resubmit. The current version overstates its sharpness and 'fundamental limitation' conclusions, so a major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the upper-bound half of this paper is worth reading; the lower-bound half is not. Theorem 1 and Theorem 3 give clean non-asymptotic bounds for Soft Best-of-n, and the O(1/n) KL rate is real — the binary example in Appendix D confirms it. But Theorem 2, the claimed converse, is false as stated. In that same binary example a direct expansion shows TV between the tilt and the soft BoN distribution is O(1/n), not Omega(1/sqrt(n)). The proof has an explicit \"we will take care of it later\" for the remainder that never gets resolved, and the Berry-Esseen step produces a spurious 1/sqrt(n) gap because the centered fluctuations do not bias the expectation at that order. That matters: the blockwise claim that the exponential sample-complexity condition \"cannot be improved in general due to our lower bound\" leans on Theorem 2, so that limitation is not established.\n\nWhat is actually new: the explicit CV-based KL bound and the relative-reward bound are new in this form. The soft-selection idea itself is a natural extension and the paper cites Puri et al., but the finite-sample guarantees are a genuine contribution. The blockwise vs. symbolwise comparison is a useful thought experiment, and the paper is honest that the i.i.d. additive model is unrealistic for LLMs; as a toy model it is fine, but it should not be sold as a fundamental limitation.\n\nOther issues: Corollary 2 and Theorem 4 have typos that make the statements inconsistent with their proofs, and the blockwise corollary drops an m in the denominator and uses epsilon instead of e^epsilon - 1. These are fixable. The paper would also benefit from engaging with importance-resampling and particle-filter literature, where soft selection is a standard trick.\n\nRecommendation: This deserves a serious referee, but the current version is not in publishable shape. The upper bounds are a solid contribution; the lower bound should be removed, corrected, or downgraded to a conjecture, and the blockwise \"fundamental limitation\" language should be softened accordingly. If the authors fix these issues, I would support publication.","headline":"Solid O(1/n) upper bounds for Soft Best-of-n, but the claimed converse (Theorem 2) is false as stated and the blockwise 'fundamental limitation' rests on it.","tokens_in":22576,"tokens_out":4510,"would_cite":true,"duration_ms":42634,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17","62B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Soft Best-of-n sampling with temperature λ converges to optimal tilt at rate 1/n.","keywords":["best-of-n sampling","soft best-of-n","exponential tilting","KL divergence","model alignment","reward maximization","sample complexity","temperature parameter"],"falsifier":"For the mathematical claim, any finite alphabet and bounded reward where the true $D_{\\mathrm{KL}}(P_\\lambda^*\\parallel P_{n,\\lambda})$ exceeds $\\log(1+\\frac{1}{n}\\mathrm{CV}(e^{r_\\lambda(X)})^2)$ would refute Theorem 1; for the practical transfer, holding $\\lambda$ fixed on a real language model and measuring the empirical KL gap as n grows should show roughly $1/n$ decay, while a plateau or much slower decay would falsify the claim that the i.i.d. guarantee carries over.","tokens_in":2013,"feed_emoji":"🎲","tokens_out":3240,"duration_ms":107032,"temperature":0.7,"pith_summary":"This paper introduces a variant of Best-of-n sampling for aligning a language model with a reward function: draw $n$ candidate responses, then pick one with probability proportional to $e^{r(x)/\\lambda}$ instead of always picking the highest-reward one. The central claim is that as $n$ grows, this Soft Best-of-n distribution approaches the optimal exponentially tilted distribution $P_\\lambda^*(x) \\propto P(x)e^{r(x)/\\lambda}$—the exact solution of the KL-constrained reward-maximization problem—with both KL divergence and relative reward gap shrinking at rate $O(1/n)$. Because $\\lambda$ interpolates smoothly between the base distribution and hard Best-of-n, a practitioner can target any point on the Pareto frontier of reward versus KL distance, which ordinary Best-of-n cannot do for small $n$. The paper also shows that in an additive-reward model for sequences, blockwise sampling needs exponentially many samples in block length, whereas symbolwise sampling decouples the required sample count from length.","feed_headline":"Soft Best-of-n provably closes gap to optimal tilt at 1/n rate","feed_subtitle":"With n samples and a tunable λ, inference-time sampling can sweep the reward-KL Pareto frontier.","key_machinery":"The central object is the Soft Best-of-n distribution $P_{n,\\lambda}(x)=P(x)e^{r_\\lambda(x)}\\mathbb{E}[1/(\\frac{1}{n}e^{r_\\lambda(x)}+\\frac{1}{n}\\sum_{i=1}^{n-1}e^{r_\\lambda(X_i)})]$, obtained in Lemma 1 by a symmetry reduction. The argument then applies Jensen's inequality to this expectation, converting the approximation gap into the coefficient of variation of $e^{r_\\lambda(X)}$; a variance bound for bounded random variables controls that coefficient when $r(x)\\in[0,1]$. A normal-approximation argument supplies the matching lower bound, and the additive reward model $r(x^m)=\\frac{1}{m}\\sum_i r(x_i)$ reduces blockwise moment ratios to $m$-th powers of per-symbol quantities, exposing the exponential sample-complexity gap.","core_discovery":"The central claim is that the distribution $P_{n,\\lambda}$ produced by Soft Best-of-n sampling—draw $n$ i.i.d. candidates from $P$ and return one with probability proportional to $e^{r(x)/\\lambda}$—approximates the tilted optimal distribution $P_\\lambda^*(x)\\propto P(x)e^{r(x)/\\lambda}$ with a quantitative gap that shrinks linearly in the sample count. Theorem 1 bounds $D_{\\mathrm{KL}}(P_\\lambda^*\\parallel P_{n,\\lambda})\\le \\log(1+\\frac{1}{n}\\mathrm{CV}(e^{r_\\lambda(X)})^2)$, hence $O(1/n)$; Theorem 3 gives the same $O(1/n)$ relative convergence in expected reward; and Theorem 2 shows the rate cannot improve in general, via a total-variation lower bound of order $1/\\sqrt{n}$ that implies an $\\Omega(1/n)$ KL lower bound. For additive sequence rewards the blockwise version inherits the same bound with $m$ in place of $1$, but the number of samples needed to reach a fixed KL target grows exponentially in block length $m$.","pith_inferences":["Because the bounds are explicit in n, $\\lambda$, and the coefficient of variation, a practitioner could estimate $\\mathrm{CV}(e^{r/\\lambda})$ from unlabeled outputs and choose n from the bound instead of grid-searching; the paper does not prescribe this diagnostic.","Per-token soft selection should dominate whole-sequence resampling whenever reward evaluations are cheap relative to generation, since the additive model shows the required n for blockwise tilting grows exponentially in sequence length; this comparison is implicit in the paper's symbolwise-versus-blockwise analysis.","A natural testable extension is to use Soft Best-of-n with step-level (process) rewards on long reasoning chains, treating each step as a 'symbol' and leveraging the symbolwise sample-complexity advantage to reduce wall-clock cost."],"forward_implications":["Soft Best-of-n is guaranteed to be $\\epsilon$-close in KL to the tilted distribution whenever $\\lambda \\ge 1/\\log(1+4n\\epsilon)$, so for fixed n a sufficiently large temperature puts the sampler on the optimal KL-reward Pareto frontier.","The relative expected-reward gap is at most $M(\\lambda)/(M(\\lambda)+n)$, meaning even moderate n nearly matches the reward of the exact tilt when $\\lambda$ is not too small.","Hard Best-of-n appears as the $\\lambda\\to 0$ limit and the base distribution as $\\lambda\\to\\infty$, so the convergence theorem interpolates between two previously studied regimes and places both relative to the tilted target.","In the additive model, blockwise Best-of-n needs $n=e^{O(m\\epsilon^2)}$ samples to beat the mean reward by $\\epsilon$, while blockwise Soft Best-of-n requires $n=O(\\epsilon^{-1}e^{cm/\\lambda'})$ samples to approximate the same tilt; symbolwise selection needs n independent of m.","The $O(1/n)$ KL rate is optimal in general: a binary example attains the coefficient-of-variation constant, and the total-variation lower bound rules out faster decay."],"supporting_citations":[{"why":"Supplies the tilted distribution $P_\\lambda^*$ that is the target of the convergence analysis.","marker":"[6]"},{"why":"Gives the variance bound used to turn the coefficient of variation into an explicit $1/n$ bound when rewards are bounded.","marker":"[36]"},{"why":"Normal-approximation theorem used to derive the total-variation lower bound behind the $\\Omega(1/n)$ KL converse.","marker":"[37]"},{"why":"Companion normal-approximation result for the same lower-bound argument.","marker":"[38]"},{"why":"Inequality converting the total-variation lower bound into a KL-divergence lower bound.","marker":"[39]"},{"why":"Establishes the asymptotic equivalence between BoN and KL-constrained fine-tuning that the finite-n result refines.","marker":"[24]"},{"why":"Provides non-asymptotic guarantees for BoN against which the Soft Best-of-n optimality result is compared.","marker":"[25]"},{"why":"Corrects earlier KL-divergence formulas for BoN, giving the tighter upper bound used as background for the soft variant.","marker":"[35]"},{"why":"Concentration inequality used to prove that symbolwise sampling decouples the required number of samples from sequence length.","marker":"[40]"}],"fun_headline_variants":["Soft Best-of-n tunes reward-KL tradeoff at 1/n rate","New sampling method hits optimal tilt with O(1/n) KL gap","Soft BoN: smooth interpolation, sharp 1/n convergence","Best-of-n generalized: tunable λ, guaranteed 1/n tilt","Soft Best-of-n achieves optimal tilt rate with additive rewards"],"cache_read_input_tokens":24576,"weakest_assumption_plain":"The blockwise sample-complexity result assumes the tokens in a response are independent and identically distributed and that the reward of a response is the sum of per-token rewards—conditions the paper itself says real language models do not satisfy; if those fail, the exponential-cost conclusion may not carry over.","fun_headline_variants_meta":{"raw":{"variants":["Soft Best-of-n tunes reward-KL tradeoff at 1/n rate","New sampling method hits optimal tilt with O(1/n) KL gap","Soft BoN: smooth interpolation, sharp 1/n convergence","Best-of-n generalized: tunable λ, guaranteed 1/n tilt","Soft Best-of-n achieves optimal tilt rate with additive rewards"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000443,"raw_usage":{"total_tokens":2253,"prompt_tokens":967,"completion_tokens":1286,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":1194}},"tokens_in":583,"tokens_out":1286,"duration_ms":9036,"temperature":1.0,"reasoning_tokens":1194,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:58:59.913145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the mathematical claim, any finite alphabet and bounded reward where the true $D_{\\mathrm{KL}}(P_\\lambda^*\\parallel P_{n,\\lambda})$ exceeds $\\log(1+\\frac{1}{n}\\mathrm{CV}(e^{r_\\lambda(X)})^2)$ would refute Theorem 1; for the practical transfer, holding $\\lambda$ fixed on a real language model and measuring the empirical KL gap as n grows should show roughly $1/n$ decay, while a plateau or much slower decay would falsify the claim that the i.i.d. guarantee carries over.","supporting_citations":[{"cited_title":"I-divergence geometry of probability distributions and minimization problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the tilted distribution $P_\\lambda^*$ that is the target of the convergence analysis."},{"cited_title":"A better bound on the variance,","cited_arxiv_id":null,"evidence_quote":"Gives the variance bound used to turn the coefficient of variation into an explicit $1/n$ bound when rewards are bounded."},{"cited_title":"The accuracy of the gaussian approximation to the sum of independent variates,","cited_arxiv_id":null,"evidence_quote":"Normal-approximation theorem used to derive the total-variation lower bound behind the $\\Omega(1/n)$ KL converse."},{"cited_title":"Concentration inequalities and martingale in- equalities: a survey,","cited_arxiv_id":null,"evidence_quote":"Concentration inequality used to prove that symbolwise sampling decouples the required number of samples from sequence length."}],"review_version":1}