{"id":"9c150b70-0cb8-497c-987b-3ab720f31701","arxiv_id":"2505.23247","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new reward reshaping method provably increases reward variance for GRPO-based RLHF training, with an O(n log n) global optimization algorithm and preliminary speedups in experiments.","lead":"This paper proposes a reward-adjustment step for GRPO, a popular RLHF training method, that provably widens the spread of reward scores while keeping their average and ranking unchanged. It also gives an O(n log n) algorithm for the resulting optimization problem, and early experiments suggest faster policy training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central speedup claim applies [24, Theorem 4] to a reward that GRPOVI recomputes each step, so higher variance of a time-varying proxy reward does not by itself prove faster convergence to the original reward.","rationale":"The reader's weakest assumption identifies the same load-bearing gap, and I agree with that identification. The variance-increase theorem itself is correct for a fixed adjusted reward, and the algorithmic construction in Section 3 appears internally consistent; I do not find a more serious flaw there. The problematic step is Section 4's 'According to theorem 1 and [24, Theorem 4]' because the reward used by Algorithm 3 is recomputed at every step and is different from the reward used for evaluation. This matters for the central claim: if the speedup cannot be traced to the proved variance increase, the paper's theoretical motivation for GRPOVI is lost, even though the small-scale experiments may still show an effect. Since the reader already conditioned on this gap, I do not change the verdict; the paper should either prove a fixed-reward or accumulated-reward version of the speedup, or soften the theoretical claim to a heuristic motivation.","tokens_in":15526,"tokens_out":18281,"duration_ms":205050,"concrete_test":"Run a fixed-reward control: at t=0, generate responses for each training prompt, solve (3) once to define a static adjusted reward r'(y)=r̃(y) for those responses and r'(y)=r(y) for all other responses; then train from πθ(0) with GRPO using r' for all T steps, evaluating on the original ground-truth reward. Compare against standard GRPO and the paper's online GRPOVI. If the fixed-reward variant does not beat standard GRPO on the original reward, the Section 4 attribution of speedup to increased initial-policy variance is not supported; if it does, the online recomputation is not needed for the theoretical explanation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The optimization core is mostly sound: for a fixed adjusted reward r' defined by patching one group G, Theorem 1 correctly shows Var_{πθ(0)}(r') >= Var_{πθ(0)}(r), and Lemma 2/Algorithm 2 plausibly solve (3). The load-bearing gap is in Section 4. GRPOVI does not train on a single fixed adjusted reward. In Algorithm 3, the rewards {r̃_i} are recomputed at every step from responses sampled from the current policy πθ(t); the adjusted reward for a given response can change between steps and even between batches. Theorem 1 and [24, Theorem 4] concern a fixed reward objective: [24, Thm 4] bounds the minimal time to raise the expected value of a specific fixed reward r, and Theorem 1 increases the initial-policy variance of a specific r'. Since the algorithm's effective reward is time-varying, the conjunction 'according to theorem 1 and [24, Theorem 4], GRPOVI achieves faster RLHF training' is not a valid derivation. Moreover, even for a fixed reward, [24, Thm 4] is a lower bound, not an upper bound, so a larger variance does not by itself guarantee that a particular algorithm runs faster. The speedup may be real empirically, but the paper's stated mechanism — higher initial variance lowers the [24] time bound — is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a reward adjustment model: for a fixed prompt and a sampled response group, it maximizes a probability-weighted second moment of the adjusted rewards subject to box constraints, a sortedness constraint, and an expectation-preservation constraint. Theorem 1 shows that a global maximizer of this model increases the reward variance of the initial policy over the response space while preserving the reward expectation and the relative ordering inside the group. Lemma 2 characterizes all extreme points of the feasible set, and Algorithm 2 is proposed as an O(n) one-pass search (O(n log n) including sorting) for a global maximizer. Section 4 integrates this into GRPO as GRPOVI: at each training step, responses are sampled from the current policy, adjusted rewards are computed using initial-policy probabilities, and the adjusted rewards are used for advantage estimation. Experiments on Pythia with two training reward models compare GRPOVI with standard GRPO using the ArmoRM reward as a proxy.","tokens_in":15798,"tokens_out":12317,"duration_ms":135616,"significance":"If the advertised speedup were established, the contribution would be valuable: it offers a low-overhead, provably variance-increasing reward transformation that preserves preferences within a group, and the extreme-point characterization is a clean optimization result. The optimization core, specifically Theorem 1 and Lemma 2 for a fixed adjusted reward, appears sound, and the O(n log n) search is elegant and is supported by simulation comparisons against exhaustive enumeration. However, the link from initial-policy variance increase to faster GRPO on the original reward is not derived: the cited theorem applies to a fixed reward and is a lower bound, while GRPOVI optimizes a time-varying adjusted reward. The experiments are also small-scale and use only reward-model proxies. The paper therefore currently establishes a useful optimization method and a plausible empirical signal, but not the stated theoretical acceleration claim.","major_comments":[{"comment":"The sentence 'According to theorem 1 and [24, Theorem 4], the GRPOVI algorithm achieves faster RLHF training compared to the original GRPO algorithm' is not a valid derivation. [24, Theorem 4] concerns a fixed reward function and gives a lower bound on the time needed to increase the expected value of that fixed reward; a larger variance only makes that lower bound smaller and does not by itself guarantee that a particular algorithm runs faster. Moreover, GRPOVI does not optimize a fixed adjusted reward: in Algorithm 3 the responses are resampled from the current policy at every step and the adjusted rewards are recomputed from those samples, so the effective reward changes between steps and between batches. Theorem 1 and Corollary 1 only show that, for one fixed adjusted reward built from one response group, the initial-policy variance is larger; they do not apply to the time-varying reward sequence used by GRPOVI, nor do they compare convergence to the original reward. Please provide a rigorous analysis for the time-varying setting or explicitly reframe the contribution as an empirically demonstrated acceleration.","section":"Section 4, Algorithm 3"},{"comment":"The paper claims that Algorithm 2 finds a global solution of (3) in O(n) time, but no correctness theorem or proof is given. Lemmas 3-5 show that certain one-step moves (k to k+1 or l to l-1) strictly increase the objective when the recomputed alpha remains in [m,M], and Lemma 4 provides a stopping condition. However, the greedy choice in lines 16-26 between the left and right moves is not shown to lead to a global maximizer: the objective is not shown to be unimodal along the bidirectional path, and the proof does not rule out that a locally smaller move would enable a much larger gain later. The agreement with exhaustive enumeration in Table 1 covers only synthetic instances and is not a proof. Please add a correctness theorem for Algorithm 2, or state the additional conditions under which the greedy path is guaranteed to reach a global optimum.","section":"Section 3.4, Algorithm 2"},{"comment":"The empirical claim that GRPOVI 'significantly' improves training efficiency rests on limited evidence. The experiments use a small base model (Pythia), group size 8, a single pass over the training prompts, and only two training reward models; the only reported performance metric is the mean ArmoRM reward on the training and test sets, with no numerical table, effect sizes, or significance tests. Figures 1 and 2 show means with standard-deviation bands, but the text does not report the final reward values or the width of the bands, so the reader cannot assess whether the differences are statistically meaningful. There is also no comparison against the downsampling baseline of [35] or other variance-based methods. This does not block the optimization contribution, but it does not by itself establish the central acceleration claim; the experimental section should either be strengthened or the conclusions should be softened accordingly.","section":"Section 5.2"}],"minor_comments":[{"comment":"The phrase 'right hind side of (4)' should read 'right-hand side of (4)'.","section":"Lemma 2 proof"},{"comment":"The variable name 'f lags' appears to be a typo for 'flag'; also, the expression 'Scm' in line 13 should be written as 'S_C m' to avoid confusion with the product S_C times m.","section":"Algorithm 2"},{"comment":"Line 8 normalizes the probabilities before solving (3), whereas Theorem 1, Lemma 2, and Corollary 1 use unnormalized probabilities pi = pi(y_i|x). Please clarify that the normalized values are conditional probabilities under the initial policy and state explicitly why the expectation-preservation and variance-increase arguments remain valid in this parametrization.","section":"Algorithm 3"},{"comment":"The 'indirect explanation' for the empirical effectiveness of rule-based rewards in DeepSeek-R1 is not empirically tested in this paper; consider labeling it clearly as a hypothesis or providing a supporting ablation.","section":"Section 4, rule-based reward discussion"},{"comment":"Please report the final checkpoint numbers and standard errors in a table or in the text, since the figures alone make it difficult for the reader to quantify the improvement claimed by the paper.","section":"Section 5.2.2"}],"recommendation":"major_revision","confidential_remarks":"The optimization core of this paper is solid and could be publishable on its own as a methods contribution. The main risk is the Section 4 leap from a fixed-reward variance lower bound to a time-varying-reward algorithm; this needs either a new proof or a substantial softening of the claims. The experiments are too small to carry the full acceleration claim by themselves. Scope in cs.LG is acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The optimization core is genuine and mostly correct. The extreme point characterization in Lemma 2 for the monotone polytope with an expectation constraint is clean, and the O(n log n) (or O(n) after sorting) one-pass algorithm is a real algorithmic contribution. Theorem 1 is also correct: for a fixed group, the adjusted reward preserves expectation and preference order and increases the initial policy's variance over the full response space. If you work on convex maximization over structured polytopes, this part is worth reading.\n\nThe soft spot is exactly where the stress-test lands. Section 4 asserts that Theorem 1 plus [24, Theorem 4] implies GRPOVI trains faster, but that doesn't follow. GRPOVI recomputes the adjusted reward at every step from responses sampled from the current policy, so the effective reward is time-varying; [24]'s bound concerns a fixed reward. On top of that, [24, Theorem 4] is a lower bound on the minimal time to increase expected reward, so a larger variance relaxes a lower bound; it does not upper-bound the training time of a given algorithm. The paper's 'according to theorem 1 and [24, Theorem 4]' is not a derivation.\n\nThe experimental evidence is modest but not useless: small Pythia models, two reward models, four runs, and the GRPOVI curve sits above GRPO on both train and test. No significance tests, no code release, and the reward-model proxy evaluation is standard but weak. The explanation that ternary adjusted rewards 'indirectly explain' DeepSeek-R1's rule-based rewards is hand-wavy: rule-based rewards encode correctness, not an arbitrary three-point quantization.\n\nWho should read this: people interested in the optimization problem itself, and RLHF practitioners who want a cheap reward-shaping heuristic to test. The paper deserves a serious referee, but the referee should require the authors to either prove a speedup result under the actual time-varying reward or soften the claim substantially. If I were handling it, I'd send it out with a request to focus the contribution on the optimization method and position GRPOVI as an empirical heuristic with preliminary evidence.","headline":"A genuine O(n log n) global algorithm for the reward-adjustment polytope is the real contribution here; the claimed GRPO speedup is asserted rather than derived.","tokens_in":16311,"tokens_out":3490,"would_cite":false,"duration_ms":36750,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"A reward adjustment that provably raises reward variance makes GRPO-based RLHF training faster.","keywords":["RLHF","GRPO","reward variance","reward adjustment","nonconvex optimization","extreme point characterization","LLM alignment","O(n log n) algorithm"],"falsifier":"Run GRPO on two reward preprocessings that give the same mean and ranking per prompt: the variance-maximizing adjusted scores from model (3), and a deliberate variance-minimizing or shuffled control. If the control trains as fast as GRPOVI, or if GRPOVI's speed advantage disappears when the reward bounds $[m,M]$ are made very tight, then the variance-increase mechanism is not what drives the observed speedup.","tokens_in":15344,"feed_emoji":"📈","tokens_out":7913,"duration_ms":71840,"temperature":0.7,"pith_summary":"The paper claims that a cheap preprocessing step on reward scores can accelerate the reinforcement-learning-from-human-feedback (RLHF) phase of large language model training. For each prompt, it replaces the group of raw reward scores with the maximally spread-out scores that still have the same mean and the same preference ranking as the originals; this provably increases the reward variance of the initial policy over the response space. Because a recent theoretical result ties higher initial reward variance to faster optimization, the paper inserts these adjusted scores into the GRPO training loop and calls the result GRPOVI. Experiments on a Pythia model with two learned reward models show GRPOVI reaching higher ground-truth reward after the same number of training steps as standard GRPO, at negligible extra cost per iteration. If correct, this gives a practical way to convert the variance-speed link into a drop-in training speedup.","feed_headline":"A three-valued reward adjustment provably speeds up RLHF training","feed_subtitle":"Preserving each prompt's mean reward and ranking, the GRPOVI adjustment reaches higher reward in fewer GRPO steps.","key_machinery":"The load-bearing object is the reward adjustment model (3): maximize $\\sum_{i=1}^n p_i z_i^2$ over adjusted scores $z_i$, where $p_i=\\pi_{\\theta(0)}(y_i|x)$ are the initial policy's probabilities for the sampled responses, subject to $m\\le z_i\\le M$, $\\sum_i p_i z_i=\\sum_i p_i r_i$, and $z_1\\ge\\cdots\\ge z_n$ when rewards are sorted descending. The objective is exactly the variance term of the initial policy restricted to the sampled responses, and the constraints encode expectation preservation and preference preservation. Lemma 2 identifies every extreme point of this feasible set as a step vector of the form $(M,\\ldots,M,\\alpha,\\ldots,\\alpha,m,\\ldots,m)$, which reduces the global search to choosing two block boundaries $k,l$; Algorithm 2 walks those boundaries inward and provably returns the global optimum. In GRPOVI, these adjusted scores $\\tilde r_i$ replace the raw rewards in the GRPO advantage normalization, and the variance increase is anchored to the initial policy via $p_i$, so it holds even when responses are generated by later policies.","core_discovery":"The central discovery is that maximizing the weighted sum of squared adjusted rewards under three constraints—preserving the weighted mean reward, keeping adjusted scores within the reward bounds, and preserving the ordering of responses by reward—always increases the variance of the initial policy's reward distribution over the response space, while leaving the reward expectation and all pairwise preference comparisons unchanged. The maximization is a nonconvex problem, in general NP-hard to solve; the paper's key structural result is that every extreme point of the feasible polytope has a three-block form: some top responses get the maximum score M, some middle responses share a value α, and the remaining responses get the minimum score m, with α determined by the mean-preservation constraint. Since a convex objective attains its maximum over a polytope at an extreme point, this characterization turns the global search into a one-pass scan over block boundaries that runs in O(n) after sorting, giving an O(n log n) algorithm overall. Plugging the adjusted rewards into the GRPO advantage estimator defines the GRPOVI algorithm, and experiments report that it beats standard GRPO on training and test rewards across checkpoints.","pith_inferences":["Beyond the paper, the three-block characterization suggests that the optimal adjusted reward for any prompt can be precomputed from the initial policy's probabilities and reward bounds, so the optimization could be replaced by a lookup or closed-form rule in production systems.","Beyond the paper, because the adjustment preserves only the expected reward and ranking, not higher moments, its benefit might depend on the reward bound width $[m,M]$; a testable extension is to compress or widen these bounds and measure whether GRPO's speedup changes accordingly.","Beyond the paper, the scheme modifies only the scalar rewards, so it could be composed with other RLHF objectives such as KL penalties or advantage clips; the paper does not test those interactions, but the same variance argument would apply if the adjusted rewards are used consistently.","Beyond the paper, a direct way to test the causal role of variance is an ablation that permutes reward scores within each group to lower variance while preserving mean and ranking; if such a control trains as fast as GRPOVI, variance increase would not be the operative mechanism."],"forward_implications":["GRPOVI reaches higher average ground-truth reward than standard GRPO after the same number of training steps, on both the training set and the test set, for both reward models tested.","The extra per-iteration cost is marginal: after sorting rewards, the one-pass search is $O(n)$, with $n$ the group size, so GRPOVI and GRPO have similar wall-clock per-iteration time.","Adjusted rewards take at most three distinct values per prompt, so the method effectively converts any dense reward model into a coarse positive/neutral/negative signal; the paper presents this as an indirect explanation for why rule-based rewards work well in GRPO systems such as DeepSeek-R1.","Because the probability weights are fixed at the initial policy, GRPOVI computes them once per response and does not need to recompute adjusted rewards under each updated policy.","The results provide practical evidence for the theoretical finding that higher initial reward variance over the response space shortens the time needed to raise expected reward."],"supporting_citations":[{"why":"Supplies the theorem that higher initial reward variance over the response space lowers the time needed to increase expected reward; this is the premise GRPOVI exploits.","marker":"[24]"},{"why":"Introduces the GRPO algorithm whose advantage estimator GRPOVI modifies.","marker":"[27]"},{"why":"Provides the two GRM reward models used as training rewards in the RLHF experiments.","marker":"[37]"},{"why":"Provides the ArmoRM model used as the ground-truth reward for evaluating trained checkpoints.","marker":"[32]"},{"why":"Documents DeepSeek-R1's rule-based reward success, which the three-valued adjustment is offered to explain.","marker":"[14]"},{"why":"Supplies the Pythia model family used as the initial policy.","marker":"[3]"},{"why":"Provides the UltraFeedback dataset used to split prompts for SFT, training, and testing.","marker":"[10]"},{"why":"Establishes that maximizing a convex function over a polyhedron is generally hard, motivating the extreme-point characterization.","marker":"[43]"},{"why":"Supplies the representation theorem used to show the convex objective attains its maximum at an extreme point of the feasible set.","marker":"[13]"}],"fun_headline_variants":["Variance boost provably speeds RLHF training","GRPOVI: Faster RLHF via reward variance increase","Reward variance increase accelerates RLHF","O(n log n) reward adjustment quickens RLHF"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedup claim rests on assuming that the variance-increase guarantee, which is proven for the initial policy's reward distribution, transfers to faster GRPO convergence on the original reward objective when training is run on the adjusted three-valued rewards; the paper invokes this link without deriving it.","fun_headline_variants_meta":{"raw":{"variants":["Variance boost provably speeds RLHF training","GRPOVI: Faster RLHF via reward variance increase","Reward variance increase accelerates RLHF","O(n log n) reward adjustment quickens RLHF"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000567,"raw_usage":{"total_tokens":2734,"prompt_tokens":1041,"completion_tokens":1693,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":657,"completion_tokens_details":{"reasoning_tokens":1631}},"tokens_in":657,"tokens_out":1693,"duration_ms":13306,"temperature":1.0,"reasoning_tokens":1631,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:51:44.251499+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GRPO on two reward preprocessings that give the same mean and ranking per prompt: the variance-maximizing adjusted scores from model (3), and a deliberate variance-minimizing or shuffled control. If the control trains as fast as GRPOVI, or if GRPOVI's speed advantage disappears when the reward bounds $[m,M]$ are made very tight, then the variance-increase mechanism is not what drives the observed speedup.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the two GRM reward models used as training rewards in the RLHF experiments."},{"cited_title":"Biderman, H","cited_arxiv_id":null,"evidence_quote":"Supplies the Pythia model family used as the initial policy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the UltraFeedback dataset used to split prompts for SFT, training, and testing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that maximizing a convex function over a polyhedron is generally hard, motivating the extreme-point characterization."},{"cited_title":"Gr¨unbaum, V","cited_arxiv_id":null,"evidence_quote":"Supplies the representation theorem used to show the convex objective attains its maximum at an extreme point of the feasible set."}],"review_version":1}