ReAPO: Retry-Aware Policy Optimization for Efficient Exploration in LLM Reasoning

1 Introduction

• Independent rollouts can repeat incorrect reasoning paths, wasting compute and providing little opportunity to learn from mistakes.The paper asks how to introduce structured dependence in sampling while assigning credit to each attempt.Source: §1 · p. 2
• ReAPO adds retries after failed responses and assigns credit to each attempt as a modification to GRPO.The approach is presented as compatible with verifier-based rewards and requires no additional supervision or auxiliary objectives.Source: §1 · p. 2
• Retries are conditioned on prior incorrect solutions, but remain independent across separate rollouts to retain parallelization.This introduces dependence within each rollout and can allocate more generated tokens to harder problems.Source: §1 · pp. 2–3
• ReAPO frames credit assignment as minimizing the expected number of incorrect attempts before a correct response, using a Stochastic Shortest Paths perspective.Under simplifying assumptions, each attempt receives its own advantage on only that attempt’s tokens.Source: §1 · p. 3

2 Preliminaries

• RLVR samples a response for a problem, scores it with a binary verifier, and optimizes expected reward over the problem dataset.The model is treated as an autoregressive policy that generates one token at a time.Source: §2 · p. 3
• GRPO samples a group of responses for each prompt and centers and normalizes their verifier rewards to estimate response-level advantages.The sampled responses come from the current policy.Source: §2 · p. 3
• For repeated-attempt reasoning, the paper casts each attempt as an action and the problem plus prior attempts as the state, with correctness as the terminal state.The cumulative cost is the number of attempts required to reach a correct solution.Source: §2 · p. 4

3 ReAPO: Retry-Aware Policy Optimization

• ReAPO adds verifier-conditioned exploration and attempt-level credit assignment to the standard GRPO pipeline.These are the method’s two key components.Source: §3 · p. 5

3.1 Verifier-Conditioned Exploration

• A rollout stops after a correct response; after an incorrect one, the model receives verifier feedback and a retry prompt before generating another response, up to a limit.Retries occur only after failures, so problems with more initial errors receive more additional generations.Source: §3.1 · p. 5

3.2 Assigning Credit with Multiple attempts

• The credit objective is to minimize expected failed attempts before success, treating a correct answer as terminal and each attempt as a constant-cost action.The derivation assumes prior attempts affect future success probabilities only through whether they were correct or incorrect, an assumption the paper describes as conservative.Source: §3.2 · p. 5
• Under the derivation’s assumptions, weighting each attempt by its unnormalized reward gives an update proportional to the negative gradient of expected failed attempts.The practical credit assignment applies each attempt’s advantage only to that attempt’s tokens, rather than distributing it across the whole trajectory.Source: §3.2 · p. 6

3.3 Implementing ReAPO

• A hard cap on attempts truncates the gradient estimator because computation grows quadratically and memory linearly with the number of attempts.The implementation also centers and standard-deviation-normalizes advantages; when all pooled rewards match, normalized advantages are zero and the problem contributes no policy-gradient signal.Source: §3.3 · pp. 7–8

4.1 Experimental Setup

• The evaluation uses four model configurations, defaults to G = 16 rollouts and K = 2 attempts, and assesses mathematical and scientific reasoning with first-response metrics unless stated otherwise.Qwen3-0.6B is trained on GSM-8K; the larger Qwen3 models and OLMo-2 use Polaris-53K, with evaluation benchmarks varying by model scale.Source: §4.1 · pp. 8–9, §4 · p. 8

4.2 ReAPO Efficiently Outperforms GRPO

• ReAPO outperforms GRPO at every training step on Qwen3-0.6B and reaches peak accuracy with 39% fewer tokens than GRPO with G = 32 and 31% fewer than GRPO with twice the steps.GRPO is competitive early when measured by generated tokens and wall-clock time, but ReAPO overtakes it and reaches higher final accuracy.Source: §4.2 · p. 9
• ReAPO improves both Mean@32 and Pass@32 over GRPO on OLMo-2 throughout training, including in token- and wall-clock-normalized comparisons within GRPO’s budget.On Qwen3-0.6B, SCoRe is less token- and compute-efficient and does not match ReAPO in Mean@32, though its Pass@32 is slightly improved.Source: §4.2 · p. 9

4.3 Gains Persist at Larger Scales

• At 1.7B and 4B, ReAPO improves on GRPO and the base model on nearly every benchmark, and its Qwen3-4B advantage persists as the inference sampling budget increases.Figure 4 shows first-attempt Pass@k for BeyondAIME, AIME 2025, MATH-500, and Minerva; curves average three seeds with standard-error shading.Source: Figure 4 · p. 10, §4.3 · p. 10

4.4 Attempt-Level Credit and Conditional Retries Matter

• ReAPO consistently outperforms Multi-Attempt GRPO and MaxRL, while the former gives failed attempts preceding a successful retry the same credit as the success.The comparison is designed to isolate the benefit of attempt-level credit from verifier-conditioned multi-turn sampling.Source: §4.4 · pp. 10–11
• Increasing the attempt budget to K = 3 yields limited gains on Qwen3-0.6B, where more than 90% of trajectories succeed within two attempts; 1.7B gains on math benchmarks are suggestive but do not extend to GPQA-Diamond.The 1.7B result is based on a single seed.Source: §4.4 · p. 11
• An alternative retry prompt has minimal performance impact, while unconditional retries use more tokens and achieve lower accuracy than ReAPO.Unconditional retries generate a second attempt even when the first answer is correct.Source: Figure 5 · p. 10, §4.4 · p. 11

4.5 Serial Sampling Encourages Exploration

• ReAPO’s second attempts quickly become unlikely to match the failed first answer, while solution coverage is maintained or improved relative to GRPO and matches MaxRL.The duplicate rate among independent first attempts is roughly comparable for ReAPO and GRPO.Source: §4.5 · p. 11

A Related Work

• Self-distillation and revision methods may require demonstrations, successful traces, or a separate supervised objective; ReAPO instead directly optimizes with verifier rewards.The cited approaches include teacher-free methods that use privileged traces, demonstrations, environment feedback, or an additional revision-training stage.Source: A Related Work · p. 17
• STaR uses verifier-conditioned sampling but trains on rationalizations prompted with the correct answer, unlike ReAPO's attempt-level advantage assignment.STaR removes the hint and retains the reasoning trace as supervised fine-tuning data.Source: A Related Work · p. 17
• ReAPO frames retries as a stochastic shortest-path problem: failed responses incur unit cost, and success is the terminal state.The resulting idealized objective is the expected number of failures before the first success; simplifying assumptions motivate ReAPO's finite-budget GRPO-style update.Source: A Related Work · p. 17
• SCoRe jointly optimizes multiple attempts with a progress bonus, whereas ReAPO retries only after verifier-confirmed failure and pools attempt rewards for response-specific advantages.SCoRe generates a second response regardless of first-attempt correctness and does not expose the first response's verifier outcome in its revision instruction.Source: A Related Work · pp. 17–18
• Other multi-attempt methods differ in credit assignment: Chung et al. do not form stage-specific group-relative advantages, while Bensal et al. reward reflections rather than attempt answers.ReAPO assigns separate advantages to each attempt's answer tokens.Source: §5 · p. 12, A Related Work · p. 18
• Unlike CAL-GRPO, ReAPO minimizes expected failed attempts before success and evaluates first-response performance; CAL-GRPO instead optimizes Ver@K.The comparison also notes that CAL-GRPO's MATH Ver@2 advantage over naive attempt-level GRPO comes primarily from stronger correction after a failed first attempt, while the naive variant has higher first-attempt success.Source: A Related Work · p. 18

B Discussion and Future Work

• In restricted answer spaces, verifier feedback can eliminate answers, so gains may reflect answer elimination rather than structured exploration.This concern is most relevant to multiple-choice and true-or-false tasks, where a failed answer can substantially narrow the remaining possibilities.Source: B Discussion and Future Work · p. 19
• On the 0.6B model, fewer than 10% of trajectories remain eligible for a third attempt after first-attempt accuracy exceeds 80% and second-attempt cumulative accuracy exceeds 90%.The third attempt provides little additional training signal and yields no clear improvement over two attempts, while sequential retries add generation cost and training latency.Source: B Discussion and Future Work · p. 19
• With a fixed cumulative response-token budget, long early attempts can leave insufficient capacity for retries; over 50% of Qwen3-4B-Base ReAPO trajectories reach maximum length near training's end, versus under 10% for GRPO.The truncation increase coincides with ReAPO's sharper validation-performance decline after about 600 steps; the authors suggest separate or adaptive per-attempt budgets.Source: B Discussion and Future Work · p. 19
• ReAPO assumes reliable verification; false negatives can penalize valid responses, while false positives can prevent useful retries.Experiments primarily cover mathematical and scientific tasks with automatically checkable answers; noisy or learned verifiers and code, tool-use, and less reliably scored domains remain future work.Source: B Discussion and Future Work · p. 19
• Verifier-conditioned rollouts and attempt-level credit assignment could also be paired with Dr.GRPO, DAPO, or MaxRL.The authors propose studying whether retry-aware exploration complements objectives designed to address other weaknesses of GRPO.Source: B Discussion and Future Work · p. 19

C Experimental Details

• Experiments use MaxRL's training and evaluation hyperparameters, except for training the SCoRe Stage-II baseline.Source: C Experimental Details · p. 20

• Qwen3-0.6B-Base is trained on GSM8K and evaluated on GSM8K-Platinum.The training data's reference answer supports verifier-based evaluation, and each problem receives a step-by-step reasoning prompt.Source: §C.1 · p. 20
• The prompt requests a boxed final answer, and an incorrect first response triggers a new user message asking the model to reflect and try something else.The appendix illustrates the format with a word problem about clips sold in April and May.Source: §C.1 · p. 20
• Training uses temperature 1.0; validation uses temperature 0.6 and top-p 0.95, with no top-k restriction.The experiments use VERL and four NVIDIA B200 GPUs; most Qwen3-0.6B runs disable the KL penalty and entropy bonus.Source: §C.1 · p. 20

• Qwen3-1.7B-Base and Qwen3-4B-Base are trained on Polaris-53K, with math verify assigning a binary correctness reward to each attempt.The Polaris-53K answer is used as the reference answer.Source: §C.2 · p. 20
• The prompt requests step-by-step reasoning and a boxed answer; an incorrect first response triggers a retry instruction in a new user message.The appendix supplies a complex-roots example and a corresponding Qwen3-1.7B/4B chat template.Source: §C.2 · pp. 20–21
• Evaluation samples 256 responses per problem for BeyondAIME, AIME 2024, AIME 2025, and HMMT 2025, and 64 for MATH-500, Minerva, and GPQA-Diamond.A separate high-sample evaluation reports Pass@k and its corresponding first-attempt mean accuracy at the selected checkpoint.Source: §C.2 · p. 21
• Training is fully on-policy, disables KL penalty and entropy bonus, and uses temperature 1.0; validation uses temperature 0.6 and top-p 0.95.The experiments use VERL and four NVIDIA B200 GPUs; the hyperparameter table aggregates seven seeds for Qwen3-1.7B and three for Qwen3-4B.Source: §C.2 · p. 21, Table 3 · p. 22

C.3 Ablation Setup

• ReAPO’s default attempt budget is K = 2; the K = 3 variant adds a retry when the first two attempts fail.Source: §C.3 · p. 22
• The retry-prompt ablation compares the default instruction with “Try again,” holding all other training settings fixed.Source: §C.3 · p. 22
• The credit-assignment baseline gives one binary reward and one trajectory-level advantage to all tokens after attempts end in success or reach the retry limit.Source: §C.3 · p. 22
• Figure 7 plots first-attempt Pass@1 and Pass@32 per benchmark during Qwen3-1.7B-Base training, averaging seven seeds with standard-error shading.Source: Figure 7 · p. 23

D.1 Per-Benchmark Training Curves

• ReAPO finishes ahead of GRPO on most Qwen3-1.7B-Base benchmarks for both first-attempt Pass@1 and Pass@32, with particularly consistent differences on BeyondAIME, MATH-500, and Minerva.Source: §D.1 · p. 23
• Qwen3-4B-Base ReAPO is stronger than GRPO on most benchmarks during the first 500–600 steps, but both methods later decline on several tasks; results use step 500, where both peaked under validation checkpoint selection.Source: §D.1 · p. 23

D.2 Solution Coverage

• ReAPO numerically exceeds GRPO on all seven benchmarks at both model scales in Pass@32; for Qwen3-1.7B-Base, the gain is significant under reported standard errors on six benchmarks.Source: §D.2 · pp. 23–24
• On GPQA-Diamond, the Qwen3-4B-Base base model retains higher Pass@32 than either trained policy.Source: §D.2 · p. 24

D.3 Token-Normalized Performance

• At overlapping token counts, ReAPO is competitive with or stronger than GRPO on most benchmarks; clearest gains occur on AIME 2025 and MATH-500 for Qwen3-4B-Base.Source: §D.3 · p. 24

D.4 Training Dynamics

• Qwen3-1.7B-Base and Qwen3-0.6B-Base retain higher actor entropy than GRPO through most training, consistent with greater stochasticity; the diagnostics do not establish that entropy causes accuracy gains.Source: §D.4 · p. 24
• For Qwen3-4B-Base, a late rise in response length and clipping coincides with declining validation performance, suggesting increasing truncation pressure without establishing causality.Source: §D.4 · p. 24
• Figure 9 shows first-attempt Pass@k for Qwen3-1.7B-Base at the last checkpoint; GRPO and ReAPO curves are means across seven training seeds, with shaded standard errors.Source: Figure 9 · p. 25
• Figure 10 plots Qwen3-1.7B-Base MATH-500 first-attempt accuracy against steps and generated tokens, comparing 4,096- and 8,192-token trajectory limits.Source: Figure 10 · p. 25
• Figure 11 tracks exact second-answer matches to failed first answers on AIME 2025 for one seed; the caption reports less repetition decrease for the smaller model.Source: Figure 11 · p. 25

D.5 Ablations on Qwen3-1.7B-Base

• ReAPO matches or exceeds GRPO with twice the group size while generating about 20% to 30% fewer tokens; with 4,096 tokens, it performs on par with GRPO at 8,192 tokens (22.1% versus 21.9%).Source: §D.5 · p. 26, Table 4 · p. 26
• Increasing the attempt budget to K = 3 slightly improves mathematical benchmarks but reduces GPQA-Diamond accuracy.Source: §D.5 · p. 26

D.6 Sequential versus Parallel Sampling

• At very small AIME 2025 sampling budgets, parallel sampling performs slightly better, but sequential retries reach parallel Pass@2048 success using approximately 1.7× fewer generated responses.Source: §D.6 · p. 26, Figure 15 · p. 30
• Table 7 reports common-phrase frequencies in first attempts and verifier-conditioned retries for Qwen3-1.7B-Base on MATH-500 at step 1,040, using one seed.Source: Table 7 · p. 27
• Table 8 reports the same phrase-frequency comparison for Qwen3-4B-Base on MATH-500 at step 500, using one seed.Source: Table 8 · p. 27
• Across overlapping token counts, Figure 12 shows ReAPO competitive with or outperforming GRPO on most Qwen3-1.7B-Base and Qwen3-4B-Base benchmarks.Source: Figure 12 · p. 28
• Figure 13 summarizes training dynamics for Qwen3-0.6B-, 1.7B-, and 4B-Base, averaging eight, seven, and three seeds by model size.Source: Figure 13 · p. 29
• Figure 14 illustrates a MATH-500 verifier-conditioned retry that revisits the initial interpretation and recovers the correct answer.Source: Figure 14 · p. 30

E Formal Derivation of ReAPO

• The analysis defines q_m as success probability on attempt m conditional on all earlier attempts failing, under a history-independence assumption.It assumes the interaction continues until a success, with finite expected stopping time.Source: E Formal Derivation of ReAPO · p. 31
• The objective is to minimize the expected number of failed attempts before the first success, assuming success occurs almost surely and expected stopping time is finite.This is motivated as a stochastic shortest path objective.Source: E Formal Derivation of ReAPO · p. 31

E.1 Derivation of the Policy Gradient Decomposition

• The derivation assumes each attempt’s success probability depends on earlier attempts only through their failure, not their specific outcomes.It further assumes the expected additional attempts quantity c_m is constant across attempt indices to simplify the policy-gradient expression.Source: E Formal Derivation of ReAPO · p. 31, §E.1 · p. 32

E.2 The Effect of Truncation

• A finite cap K truncates the objective and policy-gradient estimate by omitting contributions from attempts beyond the K-th attempt.The truncated objective counts expected failed attempts up to K.Source: §E.2 · p. 33
• With uniform q_m ≥ q_min > 0 and bounded gradients, truncation bias in the policy gradient decays exponentially with K.The analysis also gives a condition on K for the truncated objective to approximate the full objective within ε.Source: §E.2 · p. 34

E.3 The Effect of Advantage Normalization

• Centering advantages by the mean does not exactly minimize expected failed attempts, and a correction term accounts for the discrepancy while encouraging fewer attempts.The correction term is the gradient of the expected number of attempts.Source: §E.3 · p. 35
• In practice, rewards are centered and divided by their standard deviation, following GRPO, although the preceding theory uses unnormalized advantages.The paper analyzes this normalization’s effect on policy-gradient bias and variance for binary rewards.Source: §E.3 · p. 35
• Standard-deviation normalization preserves gradient direction but upweights prompts with larger expected numbers of attempts relative to easier prompts.The rescaling is about the order of E[τ] for each prompt.Source: §E.3 · p. 35