PaperlayerView exact revision on arXiv

Source-linked AI summary

Training Reasoning Models on Saturated Problems via Failure-Prefix Conditioning

Minwu Kim, Safal Shrestha, Anubhav Shrestha, Keith Ross

arXiv:2601.20829v2cs.LGcs.AIcs.CL

TL;DR

Saturated problems challenge RLVR because nearly all rollouts are correct and rewards provide little useful signal, while collecting harder problems is costly. The paper introduces failure-prefix conditioning, which initializes training from prefixes of rare incorrect trajectories to target failure-prone reasoning states. It consistently improves performance where standard RLVR stalls, matches gains from additional medium-difficulty data, improves recovery from misleading reasoning, and gains further from iterative prefix refreshing.

  • Problem

    Saturated problems provide little useful RLVR signal because failures are rare, while collecting harder unsaturated problems becomes increasingly difficult and expensive.

  • Method

    Failure-prefix conditioning appends prefixes of rare incorrect rollouts to original questions, directing RLVR exploration toward failure-prone reasoning states.

  • Results

    Failure-prefix conditioning consistently improves performance where standard RLVR stalls, achieves gains comparable to additional medium-difficulty questions, and improves robustness to misleading reasoning.

  • Takeaways & Limitations

    Saturated problems remain valuable training resources when exploration targets their sparse but informative failure modes, with iterative prefix refreshing enabling further improvement after plateaus.

  • Takeaways & Limitations

    The experiments use a relatively small model, so whether the same benefits hold at larger scales remains unresolved; collecting rare incorrect rollouts also adds considerable computational overhead.

Abstract

from arXiv · show

As Reinforcement Learning with Verifiable Rewards (RLVR) substantially improves the reasoning abilities of large language models (LLMs), a new bottleneck emerges: more training problems become saturated, that is, the LLM answers the questions correctly for nearly every rollout. On such problems, rewards provide little useful learning signal. While collecting harder problems is a natural response, it is costly and increasingly difficult. We propose failure-prefix conditioning, a simple method that unlocks the remaining signal in saturated problems by shifting exploration toward failure-prone reasoning states. By conditioning on prefixes of rare incorrect trajectories, the method improves the model's ability to recover from misleading early reasoning. We observe that failure-prefix conditioning consistently improves performance where standard RLVR stalls, and achieves gains comparable to training on newly collected medium-difficulty problems. We further analyze the model's robustness, finding that our method reduces performance degradation under misleading failure prefixes, albeit with a mild trade-off in adherence to correct early reasoning. Finally, we demonstrate that an iterative approach, which refreshes failure prefixes during training, unlocks additional gains after performance plateaus. Overall, our results show that saturated problems still contain valuable learning signal, and that failure-prefix conditioning provides an effective way to unlock it.

1 Introduction

As RLVR advances, saturated problems provide little reward signal because failures are rare and standard training largely repeats correct solutions. Failure-prefix conditioning redirects exploration toward rare incorrect reasoning states, improving learning, robustness, and continued gains from saturated data.

  • Motivation: Saturated problems yield little useful reward signal because nearly every rollout is correct, making harder data costly to collect.Informative incorrect trajectories still exist but are exceedingly sparse under standard sampling.
  • Method: Failure-prefix conditioning appends prefixes of rare incorrect rollouts to original questions, targeting failure-prone reasoning states during RLVR training.Prefix lengths are selected to produce a target rollout accuracy τ, typically τ = 0.5.
  • Results: Standard RLVR on the full MATH set or saturated subset provides negligible improvement, whereas failure-prefix conditioning yields consistent gains across math benchmarks.The gains are on par with training on an equal number of additional medium-difficulty questions.
  • Results: Failure-prefix-conditioned models recover better from misleading intermediate reasoning, with slower degradation after incorrect steps but a mild reduction in gains from correct steps.The robustness gains dominate overall, producing improved aggregate performance.
  • Iterative extension: Iteratively refreshing failure prefixes after a fixed dataset plateaus produces additional gains, indicating that updated prefixes can recover further learning signal.Previously informative prefixes may become less effective as the policy changes.
  • Conclusion: The method establishes that saturated problems remain valuable training resources when exploration is directed toward their sparse, informative failure modes.The contribution is framed as extending RLVR where standard methods stall.

2 Preliminaries: RLVR and Saturated Problems

RLVR can stall on saturated problems because nearly uniform successful rollouts produce little reward variation and weak policy updates. As rollout accuracy approaches one, the resulting learning signal diminishes.

  • RLVR Training: The training dataset consists of questions paired with verifiable ground-truth answers, and each rollout receives a binary correctness reward.
  • RLVR Training: A small constant ε prevents division by zero when the rollout-reward standard deviation is zero.
  • RLVR Training: GRPO updates the policy by minimizing a reward-weighted log-probability loss over independently sampled rollouts.
  • Saturated Problems: When all sampled rollouts are correct, normalized advantages become zero, so the policy gradient vanishes and training stalls.
  • Saturated Problems: For binary rewards, reward variance approaches zero as rollout accuracy approaches one, weakening learning signals on saturated problems.

3 Methodology

Failure-prefix conditioning redirects RLVR exploration from saturated questions toward failure-prone reasoning states. It constructs prefixes from incorrect trajectories, selects prefixes near a target accuracy, and trains on the resulting conditioned prompts.

  • Motivation: Failure-prefix conditioning starts exploration from rare incorrect reasoning states, helping the model recover from misleading early reasoning.
  • Prefix Construction: The method constructs prompts by appending prefixes of incorrect rollouts to the original questions.
  • Prefix Construction: For each incorrect trajectory, experiments sweep prefix lengths from 10% through 90%, producing K = 9 candidate prefixes per question.
  • Prefix Selection: Prefix-conditioned prompts tend to reduce rollout accuracy as prefixes become longer, allowing intermediate failure-prone states to be identified.
  • Prefix Selection: The selected prefix is the one whose estimated rollout accuracy is closest to the target τ, set to τ = 0.5 in the main experiments.
  • Training: The selected prefixes define a new training set D′, on which GRPO training proceeds using the standard procedure.

4 Main Experiment

The experiment tests failure-prefix conditioning in a high-accuracy RLVR regime and finds that it improves benchmark performance where standard RLVR on saturated data provides little benefit. The method remains effective across target accuracies, can match medium-difficulty data, and may be implemented with lower-cost fixed truncation.

  • Results: 44.5% average accuracy, a +3.9-point gain over the 40.6% base model, is achieved across five math benchmarks with failure-prefix conditioning.Standard RLVR reaches 40.9% on the full MATH set and 40.7% on the same saturated questions without conditioning.
  • Results: Failure-prefix conditioning slightly exceeds training on equal-sized medium-difficulty data, reaching 44.5% versus 44.0% average accuracy.Both approaches target training signals near intermediate rollout accuracy, but failure-prefix conditioning uses the original saturated MATH questions.
  • Robustness and sensitivity: τ = 0.25 reaches 44.2% (+3.6) and τ = 0.75 reaches 43.9% (+3.3), compared with 44.5% for τ = 0.5.The results indicate that exact target-accuracy tuning is not essential, although τ = 0.5 performs best.
  • Data mixing: Combining failure-prefix-conditioned data with unsaturated questions reaches only 42.3%, below the 44.5% achieved by conditioning alone.Unsaturated data alone reaches 41.7% (+1.1), suggesting that simple mixing can dilute the conditioning benefit.
  • Reducing overhead: Fixed truncation produces 43.9%, 44.3%, and 44.1% average accuracy for γ = 0.25, 0.5, and 0.75, respectively.These results are only slightly below explicit τ = 0.5 matching at 44.5%, while avoiding rollout-accuracy estimation for candidate prefixes.

5 Recovery From Misleading Reasoning

The recovery evaluation measures how models respond to incorrect and correct intermediate reasoning prefixes. Failure-prefix-conditioned models are more robust to misleading prefixes, but gain less from correct prefixes than baseline models.

  • Recovery from misleading reasoning: At a 30% incorrect prefix, FP-target drops 6.5 points and FP-fixed drops 3.3 points, versus 12.0 points for the base model.The slower degradation persists across prefix lengths, indicating stronger robustness to misleading intermediate states.
  • Recovery from misleading reasoning: The medium model degrades more sharply than the base and saturated models despite having similar overall accuracy.This supports the interpretation that the robustness is specific to failure-prefix conditioning rather than simply higher accuracy.
  • Correct-prefix trade-off: At a 30% correct prefix, FP-target improves 12.1 points and FP-fixed improves 12.3 points, versus 20.0 points for the base model.The smaller gains from correct prefixes hold across the evaluated prefix lengths.
  • Overall trade-off: Failure-prefix conditioning trades slightly smaller gains from correct prefixes for substantially improved robustness to misleading reasoning.The paper characterizes this trade-off as mild and limited in magnitude.

6 Iterative Failure-Prefix Conditioning

Performance with fixed failure prefixes eventually plateaus, motivating a second iteration that refreshes prefixes from the improved model. This iterative procedure produces additional gains beyond the first iteration’s peak.

  • Iteration 1: Mean reward eventually flattens during τ = 0.5 training, indicating a performance plateau with fixed failure prefixes.The plateau may reflect diminishing learning signal or increasingly off-policy prefixes as the model improves.
  • Iteration 2: The second iteration resamples responses from the improved checkpoint and reconstructs failure-prefix-conditioned datasets for questions with rollout accuracy 121–127/128.It uses both target matching with τ = 0.5 and fixed truncation with γ = 0.5.
  • Iteration 2: 45.0% for FP-target and 44.8% for FP-fixed improve on the original 44.5% checkpoint after a second conditioning iteration.Extending the first iteration alone does not surpass the 44.5% peak achieved at step 600.

7 Related Work

Related work connects this method to task-difficulty control, context-enhanced curriculum learning, and scaling exploration in RL training for LLMs. These lines of work motivate regulating learning signal and increasing useful exploration.

  • Task difficulty for RL: Prior RL studies report that learning signal and performance improvements peak when task success rates are intermediate.This motivates constructing training examples whose difficulty is neither saturated nor too hard.
  • Curriculum and context: Curriculum learning regulates task difficulty, while context-enhanced methods augment inputs with information that facilitates reasoning during training.These approaches provide related ways to shape the training context or difficulty.
  • Scaling RL training: Scaling RL training improves reasoning performance through more gradient updates or substantially more per-problem rollouts.Failure-prefix conditioning instead targets failure-prone states to increase access to informative exploration in saturated problems.

8 Conclusion

Failure-prefix conditioning extends RLVR on saturated problems by recovering learning signal from rare incorrect partial trajectories. Iteratively refreshing these prefixes can sustain improvement beyond initial plateaus.

  • Failure-prefix conditioning extends RLVR training on saturated problems where standard methods stall.
  • Initializing training from rare incorrect partial trajectories recovers learning signals and yields gains comparable to medium-difficulty tasks.
  • The approach enhances robustness to misleading reasoning while iteratively refreshed prefixes support improvement beyond initial plateaus.

9 Limitations and Future Work

The method has computational, scaling, behavioral, and domain limitations. Future work targets efficient failure sampling, larger models, preservation of correct reasoning adherence, and broader evaluation.

  • Failure-prefix conditioning requires rare incorrect rollouts, introducing considerable computational overhead.
  • The experiments use a relatively small model, so benefits at larger scales remain to be determined.
  • The method improves robustness to misleading early reasoning but may mildly reduce adherence to correct intermediate reasoning.
  • Experiments are limited to one model and mathematical reasoning, requiring evaluation across scales, model families, and domains.
  • The target-accuracy procedure estimates prefix-conditioned accuracy across candidate prefixes before selecting a prefix near the target.
  • The fixed-truncation variant keeps a fixed fraction γ of each incorrect rollout, avoiding prefix-selection overhead while preserving most benefits.

B GRPO Training Details

The appendix specifies training, prompting, reward, inference, dataset-construction, and computational settings for the RLVR experiments. It also documents substantial but reducible token overhead from saturation identification and prefix selection.

  • GRPO training uses TRL's GRPOTrainer, the Qwen-Math chat template, binary correctness rewards, and clip-higher settings with ϵ_high = 0.4 and ϵ_low = 0.2.
  • Failure prefixes are inserted immediately after the <think> token in the assistant prompt.
  • Approximately 1,200 gradient steps require about 5 days on 4 A100 80GB GPUs, or roughly 480 GPU-hours.
  • Inference measures rollout accuracy for identifying saturated questions and selecting prefixes, using the settings summarized in Table 3.
  • Evaluation uses the settings summarized in Table 4, which are also used to measure recovery from failure prefixes.
  • 3.32B tokens are used for saturation identification and 1.94B for prefix selection under the full sampling procedures.
  • Staged sampling reduces saturation-identification cost from 3.32B to 0.64B tokens, while coarser prefix selection reduces 1.94B to 0.11B tokens.

F Additional Experiment: Addressing Response Length Issue

Additional experiments address response-length fairness and derive how GRPO-style objectives weight questions under binary rewards. The controls leave the main comparison unchanged, while the derivation links question weight to reward variability.

  • Counting failure prefixes toward the 8,000-token limit yields 44.3% average accuracy versus 44.5% originally.
  • Increasing the medium-difficulty baseline limit to 12,000 tokens improves its average accuracy from 44.0% to 44.4%, remaining comparable to failure-prefix conditioning.
  • Both second-iteration variants improve over the first-iteration checkpoint, with target accuracy achieving the best average performance.
  • The derivation uses a GRPO-family surrogate objective with likelihood ratios, advantages, and non-decreasing functions separating advantage sign and magnitude.
  • Under binary rewards, GRPO-style objectives implicitly weight each question by the standard deviation of its reward distribution.
  • Questions that are nearly always correct or nearly always incorrect receive vanishing weight, while intermediate-difficulty questions are emphasized.
Loading 2601.20829v2…