{"id":"e12f4505-4e24-4e90-8080-ecba51ca25eb","arxiv_id":"2505.20686","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new RL algorithm estimates the optimal value function offline from the reference model and then regresses the policy log-ratio to the optimal advantage, enabling single-rollout per prompt training with competitive accuracy and up to 2x speedup.","lead":"Researchers propose A*-PO, a two-stage reinforcement learning method for fine-tuning LLMs on math reasoning. It pre-computes an optimal value estimate offline from the base model, then trains with one response per prompt, cutting training time and memory while matching accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 3 (v_ref>0) is not verified on the unfiltered competition training sets, so the \"no-exploration\" theorem does not formally cover the headline AIME/HMMT results; the paper honestly flags this, but the claim is conditional on a premise the experiments do not establish.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing condition: Assumption 3 in Section 5. My stress-test agrees that this is the point where the central theoretical claim is least secure. The paper is honest about the limitation -- it states that RL post-training is not expected to solve prompts with Pass@50=0 -- but the main experiments are unfiltered, so the theorem's premise is not satisfied on the empirical distribution actually used for the headline comparisons. This is not an internal inconsistency; it is a scope mismatch between a conditional theorem and an unconditional empirical claim, which is precisely the kind of issue that should keep the verdict at CONDITIONAL. I did not select the two-beta implementation mismatch (Section 4 uses beta1 != beta2 while the theory assumes a single beta) as the primary attack, because it is a theory-practice gap that could be closed by analysis or by setting beta1=beta2, whereas the v_ref condition is a structural property of the data that the method does not control. I also did not select the memory-reduction overclaim in the abstract (Table 1 shows over 30% memory reduction only for 1.5B-vs-REBEL, not generally against PPO and GRPO), because that is a reporting issue rather than a load-bearing element of the method's validity. The paper deserves credit for releasing code, including the filtering ablation, and for stating the v_ref limitation explicitly; those features make the concern addressable rather than fatal.","tokens_in":30259,"tokens_out":8954,"duration_ms":108061,"concrete_test":"Using the released code and the exact pi_ref checkpoints, draw N=50 (or larger, e.g., 200) responses from pi_ref for every prompt in the MATH and OpenR1 training splits and compute the fraction of prompts with zero successes. Also estimate v_ref as the minimum observed Pass@1 (or a 1/50 lower-confidence bound) and plug it into the third term of Eq. (2) with N=8. If a nontrivial fraction has zero Pass@50, or if the resulting bound exceeds 0.1, then Assumption 3 fails or is vacuous for the unfiltered distribution. A decisive companion run: train A*-PO on the filtered subset (all prompts with Pass@50>0) and compare MATH500/AIME accuracy with the unfiltered Table 1-2 numbers; if filtered accuracy is no worse, the unfiltered headline is not covered by the theory, and the no-exploration claim should be restated as applying only to the filtered regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical assertion in Section 5 -- that KL-regularized RL with beta>0 and v_ref>0 can be solved without any sophisticated exploration -- rests entirely on Assumption 3: E_{y~pi_ref(·|x)}[r(x,y)] >= v_ref > 0 for every prompt x in the training distribution. Theorem 1's third error term contains (min{exp(1/beta)-1, 1/v_ref})^2 inside a 1/4 power, so the guarantee becomes vacuous as soon as v_ref is small. On the MATH and OpenR1 training sets used for the main experiments, this premise is not established: the paper's own filtering ablation (Section 4.4, Figure 4) shows that a material fraction of prompts have zero Pass@N even for moderately large N, and filtered training actually outperforms unfiltered training on MATH500. For AIME/HMMT, the paper explicitly says it does not expect RL post-training to solve prompts whose Pass@50 under pi_ref is zero. Thus the theorem formally applies only to the filtered subpopulation, while the abstract's \"without exploration\" claim and Tables 1-2 cover the unfiltered set. This is not a purely technical gap: when Pass@N=0, the estimated V* is a downward-biased constant for that prompt, so the regression target carries no learning signal, and the no-exploration guarantee is doing exactly the work the headline needs it to do.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces A*-PO, a two-stage reinforcement learning algorithm for fine-tuning LLMs on mathematical reasoning. Stage 1 estimates the KL-regularized optimal value function V* offline by sampling N responses per prompt from the reference policy and using the closed-form expression V*(x) = β log E_{πref}[exp(r/β)]. Stage 2 performs on-policy updates with one generation per prompt, regressing β log(π/πref) against the estimated optimal advantage r - \\hat V*. The authors prove a no-regret reduction (Theorem 1) showing that, under realizability, boundedness, and a positive reference success probability assumption, the KL-regularized objective can be optimized without explicit exploration. Experiments on GSM8K, MATH, and AIME/HMMT with Qwen2.5 models report competitive or better accuracy than PPO, GRPO, and REBEL, with lower training time, memory usage, and KL divergence to the base policy.","tokens_in":30600,"tokens_out":11176,"duration_ms":125606,"significance":"If the results hold as stated, the paper makes a useful contribution: it replaces critics and multiple online rollouts with a single offline-estimated value and one generation per prompt, which is conceptually clean and practically attractive. The theoretical reduction is a standard and credible no-regret argument, and the gradient identity in Lemma 3 is correct as far as I checked. The empirical tables and ablations are reasonably thorough, and the provided implementation link and appendices are strengths. The significance is diminished, however, by a mismatch between the theoretical guarantee and the implemented algorithm (two different β's), and by an unverified structural assumption that the headline 'no exploration' claim relies on. The method appears genuinely competitive, but the abstract and introduction overstate the scope of the guarantees.","major_comments":[{"comment":"The theoretical guarantee is proved for Algorithm 1 with a single β used in both Stage 1 and Stage 2, but the experiments use β1=1/2 for estimating V* and β2=1e-3 for the regression loss. These are not interchangeable: \\hat V_{β1}^* estimates V* for β1, whereas the Stage 2 loss corresponds to a KL-regularized objective with coefficient β2. For β2=1e-3 and any prompt with positive reference success probability, V*_{β2}(x) is approximately 1, while \\hat V_{β1}^*(x) can be substantially smaller; the minimizer of (β2 log(π/πref) - (r - \\hat V_{β1}^*))^2 is therefore not π*_{β2} in general. As written, the theory does not cover the evaluated algorithm. The authors should either prove a two-β variant or report experiments with β1=β2 and show that the results are preserved.","section":"Section 4 vs Section 5, Theorem 1"},{"comment":"The 'no exploration' theorem requires min_x p_ref(x) ≥ v_ref > 0, and its third error term degrades as (1/v_ref)^2 whenever v_ref < 1/(exp(1/β)-1). The paper does not verify this premise on the unfiltered MATH or OpenR1 training sets used for the main experiments. Section 4.4's filtering ablation (Figure 4) shows a material fraction of prompts with zero correct responses among N samples, and Section 6 concedes that problems with Pass@K=0 under πref are not expected to be solved by RL post-training. For such prompts \\hat V^*(x)=0, producing a downward-biased regression target and no correct-response learning signal. The theorem formally applies only to the filtered subpopulation, while the abstract and Tables 1-2 describe unfiltered runs. The authors should report Pass@N distributions on the training sets and either restrict the theoretical claim to filtered training or provide evidence for Assumption 3 on the full sets.","section":"Section 5, Assumption 3 and Theorem 1; Section 4.4"},{"comment":"The efficiency claim is not supported uniformly across all baselines. The 'up to 2x' training-time reduction in Table 1 is only against PPO and GRPO (e.g., 20.53 vs 11.01 h at 7B); against REBEL the largest speedup is 14.67 vs 11.01 h, roughly 1.33x. The 'over 30%' peak-memory reduction occurs only against REBEL at 1.5B and 3B (34.3% and 33.7%); against PPO and GRPO the memory savings are much smaller, and at 7B the reduction versus REBEL is about 22.5%. The abstract and Section 4.1 should disaggregate these claims by baseline rather than presenting them as uniform improvements over PPO, GRPO, and REBEL.","section":"Abstract and Table 1"}],"minor_comments":[{"comment":"There is a typo in the sentence 'the smallest KL divergence to the base mdoel πref'; 'mdoel' should be 'model'.","section":"Section 4.2"},{"comment":"The caption says 'across four baselines and three model sizes,' but the figure shows three baselines (PPO, GRPO, REBEL) plus A*-PO as the proposed method; 'four methods' would be more accurate.","section":"Figure 2 caption"},{"comment":"The optional filtering line in Algorithm 1 is described as optional, but Section 4.4 shows that filtering materially changes training time and can improve MATH500 accuracy; the main text should state more prominently that the main results use unfiltered training and explain why the theoretical assumptions are expected to hold in that setting.","section":"Algorithm 1, line 6 and Section 4.4"},{"comment":"The displayed derivation of the gradient identity changes notation from 2β to 2β^2 without an explicit justification; adding one sentence explaining that the constant tracks the coefficient β in the loss would improve readability.","section":"Appendix F, proof of Lemma 3"},{"comment":"Corollary 1 and Corollary 2 present nearly identical bounds and are both labeled informal; clarifying which statement is exact and which is informal, and why both are needed, would help the reader.","section":"Section 5, Corollaries 1 and 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript fits the scope of a machine learning venue and the authors appropriately cite related work such as REBEL and Q#. My main concern for the editor is that the abstract and introduction promise a no-exploration guarantee for the implemented algorithm, while the formal theorem covers a single-β variant under an unverified v_ref>0 assumption, and the implemented two-β version is not covered by the theorem. These issues are fixable by tightening the claims, adding a two-β analysis, or running β1=β2 experiments; I do not see a fundamental flaw that would require rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: A*-PO is a clean, practical method for RLVR that replaces online advantage estimation with an offline estimate of V* plus one generation per prompt, and it largely works. The experiments show competitive math accuracy with roughly 1.5–2x less training time than PPO/GRPO and substantially less memory than REBEL. The theory is a standard no-regret reduction and is internally consistent; the surprise is modest but real: with a realizability assumption, you don't need policy completeness or explicit exploration.\n\nWhat's new: the two-stage design—offline log-sum-exp estimate of V* from reference-policy samples, then single-sample on-policy least-squares regression of beta log(pi/pi_ref) to the estimated optimal advantage—is a genuine twist on REBEL, which regresses relative rewards online, and on Q#, which learns a token-level critic. The loss is simple and removes clipping and reward normalization. The paper also ships code and includes ablations on N and beta, which is good practice.\n\nWhere it's softer: the abstract's memory claim overstates the data. Across Tables 1, the >30% peak-memory reduction holds only against REBEL at the two smaller sizes; against PPO and GRPO the savings are small or negligible. That's still fine, but the headline should say 'vs REBEL' or give the range. More substantively, Theorem 1 requires Assumption 3: E_{y~pi_ref}[r(x,y)] >= v_ref > 0 for every prompt. The paper's own filtering ablation shows a material fraction of prompts have zero pass@N, and the authors acknowledge they don't expect RL to solve prompts where pass@50 is zero under pi_ref. So the theorem formally covers only the filtered subpopulation, while the abstract's 'without exploration' claim and Tables 1–2 cover the unfiltered set. This is a gap between theory and the headline experiments, but it's honestly flagged in Sections 5–6, and empirically filtering barely changes MATH500 accuracy, so it looks like a caveat rather than a load-bearing flaw. The practical two-beta implementation (beta1 in stage 1, beta2 in stage 2) is also not exactly the single-beta objective analyzed; that's a minor mismatch common in this literature. Finally, no repeated seeds are reported, so the accuracy differences between methods are within likely noise for many cells; the speed/memory differences are large enough to be credible regardless.\n\nBottom line: this is a solid contribution that deserves a serious referee. It will be most useful to practitioners designing efficient post-training pipelines and to theorists working on policy optimization with verifiable rewards. I'd cite it as a strong baseline for fast RLVR, and it's worth a reading-group slot, mainly to discuss how much the v_ref>0 assumption limits the scope.","headline":"A genuinely useful, simple RLVR method with a clean theoretical reduction that is slightly over-sold in the abstract, and a theory whose main assumption (v_ref>0) is not formally verified on the unfiltered training sets.","tokens_in":31135,"tokens_out":3079,"would_cite":true,"duration_ms":28390,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A*-PO: regressing the optimal advantage, estimated offline from the reference policy, makes RL for LLM reasoning up to 2x faster and over 30% lighter on memory without losing accuracy.","keywords":["A*-PO","optimal advantage regression","KL-regularized reinforcement learning","LLM reasoning","offline value estimation","least-squares policy optimization","rule-based rewards","no-exploration RL"],"falsifier":"Train A*-PO and an exploration-based method (PPO or GRPO) on a reasoning dataset containing many prompts whose Pass@50 under the reference policy is zero, such as competition problems the base model cannot solve, and compare held-out accuracy: if A*-PO stagnates at the base model's level while the baselines improve, the no-exploration claim is bounded by the positive-$v_{\\text{ref}}$ assumption; if all methods stagnate, the premise that RL post-training cannot solve zero-pass problems is confirmed.","tokens_in":1650,"feed_emoji":"⚡","tokens_out":2034,"duration_ms":84063,"temperature":0.7,"pith_summary":"This paper proposes A*-PO, a two-stage policy optimization method for fine-tuning LLMs on reasoning tasks. The first stage samples responses from the reference policy to estimate the optimal value function V* offline; the second stage updates the policy with a single online generation per prompt, regressing the log-ratio of the policy and reference policy toward the optimal advantage. The paper shows, both theoretically and empirically, that this simple regression achieves near-optimal performance on KL-regularized RL without explicit exploration, critics, or reward normalization. If the claims hold, reasoning RL becomes roughly twice as fast and over 30% lighter on memory while matching the accuracy of PPO, GRPO, and REBEL.","feed_headline":"A*-PO: RL for LLM reasoning at 2x speed, no critic network","feed_subtitle":"Estimating the optimal value offline, A*-PO trains with one rollout per prompt and matches PPO/GRPO/REBEL on math benchmarks.","key_machinery":"The central object is the optimal advantage function $A^{\\star}(x,y) = r(x,y) - V^{\\star}(x)$, used as the regression target. $V^{\\star}$ is recovered in closed form as a log-sum-exp expectation under the reference policy, so it can be precomputed offline. The squared loss on $\\beta \\ln(\\pi/\\pi_{\\text{ref}})$ is convex in the log-ratio and is zero at the optimal policy for any sampling distribution, so a no-regret online oracle (online gradient descent or follow-the-perturbed-leader) can minimize it without exploration; the decoupling coefficient measures the sample complexity of that minimization.","core_discovery":"The central claim is that the optimal policy of the KL-regularized RL objective can be learned by least-squares regression onto the optimal advantage, with no exploration mechanism. Because the optimal value has the closed form $V^{\\star}(x) = \\beta \\ln \\mathbb{E}_{y\\sim\\pi_{\\text{ref}}(\\cdot|x)}[\\exp(r(x,y)/\\beta)]$, it can be estimated offline from reference-policy samples. The on-policy update minimizes $\\ell(\\pi) = \\mathbb{E}_{(x,y)\\sim\\pi}[\\, (\\beta \\ln \\frac{\\pi(y|x)}{\\pi_{\\text{ref}}(y|x)} - (r(x,y) - V^{\\star}(x)))^2\\,]$, whose global minimizer is $\\pi^{\\star}$. The paper proves that with realizability, bounded losses, and a positive reference-policy success probability, the performance gap to $\\pi^{\\star}$ decays at polynomial rates in both the number of offline samples $N$ and online iterations $T$, and that the final iterate of online gradient descent converges at rate $\\widetilde{O}(1/\\sqrt{T})$ for log-linear policies.","pith_inferences":["Because Stage 1 already flags prompts where none of the N samples are correct, the same offline estimate could be reused as a training-data filter; the paper's ablation shows filtering removes roughly a quarter of the training time without hurting MATH500 accuracy, so a production pipeline could make the filter adaptive to per-prompt pass rates.","The trajectory-level formulation appears to be what avoids exponential vocabulary dependence: by querying the ground-truth reward, the analysis sidesteps the token-level critic that prior work requires, which suggests similar offline value estimation could accelerate token-level RLHF pipelines that lack a verifiable reward.","The regression objective is convex in the log-ratio, so any improvement in online convex optimization oracles would transfer directly to better sample complexity for LLM reasoning; pairing the loss with sharper no-regret algorithms is a concrete way to tighten the current bounds.","A fixed $N=8$ may be wasteful for easy prompts and insufficient for hard ones; an adaptive allocation that spends more Stage-1 samples where the reference policy's pass rate is low should reduce the bias term in Theorem 1 exactly where it matters most."],"forward_implications":["RL post-training for reasoning can be run with one online rollout per prompt, eliminating the cost of multi-generation baselines and critic networks.","Training time drops by up to 2x and peak memory by over 30% versus PPO, GRPO, and REBEL, without sacrificing accuracy across GSM8K, MATH, and competition-level benchmarks.","The final policy stays closer to the reference model (smallest KL divergence), which reduces distribution shift during training.","The theory implies that explicit exploration, such as optimism in the face of uncertainty, is unnecessary whenever the reference model has nonzero probability of solving the training prompts, making the algorithm simpler and more stable.","For log-linear policies, A*-PO converges in the last iterate with a dimension-free rate, unlike prior policy-gradient and regression-based methods that require mixing over policies or stronger structural assumptions."],"supporting_citations":[{"why":"The PPO baseline that A*-PO is compared against; it requires an explicit critic network, which A*-PO removes.","marker":"[Schulman et al., 2017]"},{"why":"The GRPO baseline that uses multiple on-policy generations per prompt; A*-PO needs only a single generation.","marker":"[Shao et al., 2024]"},{"why":"REBEL, the regression-based policy-optimization baseline and the closest competitor in the runtime and memory comparisons.","marker":"[Gao et al., 2024a]"},{"why":"FTPL no-regret oracle used in the theory to guarantee sublinear regret when learning log-linear policies.","marker":"[Suggala and Netrapalli, 2020]"},{"why":"Online gradient descent oracle, which matches the practical implementation and supplies the regret bound entering Theorem 1.","marker":"[Hazan et al., 2016]"},{"why":"Freedman's inequality, used in the proof of Theorem 1 to control martingale noise in the least-squares losses.","marker":"[Beygelzimer et al., 2011]"},{"why":"Source of the decoupling coefficient, the structural complexity measure that converts the regression bound into a performance gap.","marker":"[Zhang, 2023]"}],"fun_headline_variants":["A*-PO: 2x faster RL for LLM reasoning, no critic","Optimal advantage regression speeds LLM reasoning RL by 2x","A*-PO: offline value estimation, one rollout per prompt","A*-PO matches PPO/GRPO on math with no critic network"],"cache_read_input_tokens":33280,"weakest_assumption_plain":"The estimate of the optimal value is only accurate, and the theorem's rate is only valid, if every training prompt has a reference-policy success probability bounded above zero; prompts the base model never solves fall outside the guarantee.","fun_headline_variants_meta":{"raw":{"variants":["A*-PO: 2x faster RL for LLM reasoning, no critic","Optimal advantage regression speeds LLM reasoning RL by 2x","A*-PO: offline value estimation, one rollout per prompt","A*-PO matches PPO/GRPO on math with no critic network"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000814,"raw_usage":{"total_tokens":3614,"prompt_tokens":1035,"completion_tokens":2579,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":2509}},"tokens_in":651,"tokens_out":2579,"duration_ms":19409,"temperature":1.0,"reasoning_tokens":2509,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:49:02.229060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train A*-PO and an exploration-based method (PPO or GRPO) on a reasoning dataset containing many prompts whose Pass@50 under the reference policy is zero, such as competition problems the base model cannot solve, and compare held-out accuracy: if A*-PO stagnates at the base model's level while the baselines improve, the no-exploration claim is bounded by the positive-$v_{\\text{ref}}$ assumption; if all methods stagnate, the premise that RL post-training cannot solve zero-pass problems is confirmed.","supporting_citations":[],"review_version":1}