PaperlayerView exact revision on arXiv

Source-linked AI summary

POPE: Learning to Reason on Hard Problems via Privileged On-Policy Exploration

Yuxiao Qu, Amrith Setlur, Virginia Smith, Ruslan Salakhutdinov, Aviral Kumar

arXiv:2601.18779v1cs.LGcs.AIcs.CL

TL;DR

Hard problems often yield no correct on-policy rollout, so RL receives no learning signal, while standard exploration and easy-problem transfer can destabilize optimization or reinforce already-solvable problems. POPE instead uses short oracle-solution prefixes to guide on-policy exploration without using oracle solutions as targets. It expands hard-problem solvability and improves pass@1 and pass@16 on challenging benchmarks.

  • Problem

    On-policy RL often samples no correct rollout on hard problems, yielding zero reward and no learning signal for improvement.

  • Method

    POPE conditions hard-problem rollouts on short human- or oracle-provided solution prefixes while training with on-policy RL rather than target-based supervision.

  • Results

    POPE expands solvability, including up to 58% pass@1 and 83% pass@16 versus 48% and 77% for the base model on AIME 2025 and HMMT 2025.

  • Takeaways & Limitations

    Guided oracle information can transfer to unguided reasoning through a synergy between instruction-following and reasoning.

  • Takeaways & Limitations

    POPE lacks formal theoretical guarantees and may violate assumptions including oracle realizability, uniform prefix coverage, and absent update interference.

Abstract

from arXiv · show

Reinforcement learning (RL) has improved the reasoning abilities of large language models (LLMs), yet state-of-the-art methods still fail to learn on many training problems. On hard problems, on-policy RL rarely explores even a single correct rollout, yielding zero reward and no learning signal for driving improvement. We find that natural solutions to remedy this exploration problem from classical RL, such as entropy bonuses, more permissive clipping of the importance ratio, or direct optimization of pass@k objectives, do not resolve this issue and often destabilize optimization without improving solvability. A natural alternative is to leverage transfer from easier problems. However, we show that mixing easy and hard problems during RL training is counterproductive due to ray interference, where optimization focuses on already-solvable problems in a way that actively inhibits progress on harder ones. To address this challenge, we introduce Privileged On-Policy Exploration (POPE), an approach that leverages human- or other oracle solutions as privileged information to guide exploration on hard problems, unlike methods that use oracle solutions as training targets (e.g., off-policy RL methods or warmstarting from SFT). POPE augments hard problems with prefixes of oracle solutions, enabling RL to obtain non-zero rewards during guided rollouts. Crucially, the resulting behaviors transfer back to the original, unguided problems through a synergy between instruction-following and reasoning. Empirically, POPE expands the set of solvable problems and substantially improves performance on challenging reasoning benchmarks.

1. Introduction

On-policy RL often cannot obtain a correct rollout on hard problems, leaving no learning signal. The paper introduces POPE, which uses oracle solution prefixes to guide on-policy exploration without treating them as training targets.

  • Fewer than 50% of DAPO-MATH-17K problems produce a correct rollout for Qwen3-4B-Instruct with K=32 and a 16k token budget.
  • Token-level exploration methods and easy-problem transfer are investigated as ways to improve hard-problem exploration.
  • Mixing easy and hard problems can sharpen the model on easy problems before hard-problem progress, creating ray interference.
  • Oracle traces are expensive as training targets, while distillation can cap RL gains and off-policy training can destabilize RL.
  • POPE conditions hard-problem rollouts on short prefixes of human- or oracle-provided solutions while keeping the RL exploration on-policy.
  • 10% more hard-subset problems are solved by POPE at pass@16 with 64 rollouts and a 32k token budget.

2. Preliminaries and Notation

The paper models each rollout as receiving a binary correctness reward and uses pass@k to measure whether parallel attempts can produce a successful signal. When all sampled attempts fail, normalized on-policy updates vanish and training stalls on that problem.

  • Each problem x and rollout y receive a binary reward r(x,y) indicating whether the final answer is correct.
  • pass@k measures the probability that at least one of k independent attempts succeeds, capturing parallel exploration during training.
  • When all n rollouts fail, every normalized advantage is zero and the gradient update for that problem is exactly zero.
  • A hard problem has approximately zero base-model pass@k for sufficiently large k, while an easy problem does not meet that criterion.
  • Low output-length budgets can underestimate pass@k and make easy problems appear artificially hard.
  • The default implementation uses streaming asynchronous GRPO without entropy or KL terms, with clipped surrogate updates and low and high thresholds.

3. Why is Naïve Exploration Insufficient on Hard Problems?

Classical exploration bonuses, permissive clipping, pass@k optimization, and transfer from easy problems do not reliably solve hard-problem exploration. These approaches either produce optimization pathologies or focus learning on already-solvable problems through ray interference.

  • Token-Level Exploration on Hard Problems: Entropy bonuses and higher clip ratios increase entropy without meaningfully improving hard-problem solvability.
  • Token-Level Exploration on Hard Problems: Higher clip ratios can shift probability toward rare positive traces but may create uncertainty and effectively random exploration.
  • Ray Interference Inhibits Exploration via Transfer: Mixing easy problems with hard ones accelerates early hard-set gains but plateaus below hard-only training and can solve fewer hard problems.
  • Ray Interference Inhibits Exploration via Transfer: Unrelated easy problems preferentially improve easy-problem objectives while hard-problem progress stagnates, illustrating negative interference.
  • Pass@k Optimization: Pass@k optimization does not improve solvability when initial success probabilities are near zero and increasing k degrades performance relative to pass@1.
  • Ray Interference Inhibits Exploration via Transfer: Ray interference causes stagnation and inefficient improvement because on-policy optimization favors reward on already-successful states.

4. POPE: Privileged On-Policy Exploration

POPE uses oracle-derived prefixes to guide fully on-policy exploration on hard problems without treating oracle solutions as training targets. Training on guided and unguided variants enables learned reasoning behaviors to transfer back to unguided problems.

  • Approach: POPE steers on-policy rollouts with short oracle-solution prefixes rather than training directly on oracle solutions.The approach conditions the model on partial solutions and instructs it to build upon them, while exploration remains on-policy.
  • Guidance construction: POPE selects the shortest prefix that lets the base model obtain at least one successful rollout, using a fallback prefix when no tested prefix succeeds.Prefixes are evaluated at coarsely spaced lengths; if none works, a randomly chosen prefix shorter than one quarter of the oracle solution is used.
  • Training setup: POPE trains on a 1:1 mixture of unguided hard problems and their guided variants.The guided set is formed by augmenting hard problems with oracle prefixes and system instructions for completing the partial solutions.
  • Results: 17?

5. Why Does POPE Work?

POPE transfers learning from guided to unguided problems by exploiting instruction following, reasoning-trajectory overlap, and backtracking. An intervention that suppresses revisiting guidance improves guided performance but reduces unguided transfer, supporting the stitching hypothesis.

  • 5.1. A Mental Model: POPE makes sparse-reward exploration easier by using guidance to reach states from which successful continuations can be learned.The learned continuations then allow unguided rollouts to seek nearby successful states rather than discovering reward entirely from scratch.
  • 5.1. A Mental Model: Instruction following lets the model use unlikely oracle-prefix tokens to reach favorable internal states and obtain non-trivial reward on guided problems.The mechanism depends on the base model understanding and building upon the provided guidance.
  • 5.1. A Mental Model: Backtracking and revision expand overlap between guided and unguided state visitation, allowing learned guided behaviors to transfer.Reasoning traces can revisit nearby states and construct successful continuations from states plausibly reachable without guidance.
  • 5.2. Empirically Validating the Stitching and Overlap Hypothesis: Suppressing restatement and backtracking improves guided performance but lowers pass@32 on unguided problems.The intervention biases learning toward behaviors that succeed only when guidance is present, providing evidence that overlap is important for POPE’s efficacy.
  • 5.2. Empirically Validating the Stitching and Overlap Hypothesis: Default-instruction unguided solutions reproduce concepts and intermediate steps from guided traces, unlike outputs from the modified instruction.The qualitative comparison supports the claim that POPE stitches reasoning learned under guidance into unguided solutions.

6. Experimental Evaluation

POPE improves learning on hard problems during RL, including broad mixtures containing easy problems, and transfers gains to standardized benchmarks. Comparisons with oracle-target methods show that using oracle information as guidance is more effective than using it for SFT targets.

  • Solvability during training: POPE solves more hard training problems, with “hard + guide” continuing to improve while “hard + easy” plateaus from interference.The evaluation uses pass@32 with a 32,768-token budget, stressing whether training makes progress on hard problems.
  • Broad problem mixtures: 14.3% pass@1 and 38.9% pass@16: “hard + guide + easy” nearly matches guided training without easy problems on the hard set.The corresponding “hard + guide” scores are 15.5% pass@1 and 42.5% pass@16.
  • Broad problem mixtures: 14.0% pass@1 and 36.4% pass@16: guidance preserves strong hard-set performance even with 1K easy problems.Without guidance, adding 1K easy problems reduces hard-set performance to 2.2% pass@1.
  • Oracle-target comparisons: Full-oracle SFT reduces hard-set pass@1 from 13.6% to 2.0% and pass@16 from 32.9% to 12.4%.The degradation also appears on AIME 2025 and HMMT 2025.
  • Oracle-target comparisons: Rejection-sampled SFT reaches only 5.1% pass@1 and 24.5% pass@16 on the hard set, below both unguided and guided RL.Applying RL after this warm start yields virtually no additional hard-problem solvability gains over standard RL.

7. Related Work

Related work frames hard-problem RL as an exploration problem that standard bonuses, pass@k objectives, easy-problem transfer, and off-policy traces do not reliably solve. POPE instead uses instruction following to steer on-policy rollouts while avoiding several assumptions required by classical exploration theory.

  • Exploration methods: Hard-problem RL often makes little progress because standard on-policy exploration over-optimizes already-solvable problems and leaves harder problems unsolved.When pass@1 is near zero, token-level exploration and pass@k optimization provide little useful signal.
  • Transfer and interference: Mixing easy and hard problems can sharpen the model on easy data before improving hard problems, producing ray interference.This differs from transfer approaches that assume skills from easier problems will guide hard-problem exploration.
  • Guided exploration: POPE uses solution prefixes to steer on-policy rollouts into analogous internal states rather than performing hard resets or explicit state visitation.The method relies on instruction-following capabilities to transfer guided behaviors back to unguided problems.
  • Theoretical scope: The paper does not establish formal theoretical guarantees and notes that POPE may violate realizability, coverage, and no-interference assumptions.These violations motivate new theoretical abstractions for exploration in LLMs.
  • Off-policy learning: Off-policy traces can be unstable because suitable reasoning traces are scarce and may mismatch the model’s native reasoning behavior.Prior approaches may require reward shaping, entropy control, or careful tuning for stable learning.

8. Discussion and Perspectives on Future Work

The paper concludes that POPE addresses hard-problem exploration by combining partial oracle guidance with on-policy learning, with transfer back to unguided problems enabled by instruction following and reasoning. It also identifies formalization and knowledge-limited tasks as important boundaries for future work.

  • Conclusions: POPE guides on-policy exploration with partial oracle solutions without using them as training targets, enabling learning signal on hard problems.Guided and unguided problems are mixed so learned behaviors can transfer back to original prompts.
  • Conclusions: POPE substantially expands the set of solvable hard problems, with transfer enabled by a synergy between instruction-following and reasoning behaviors.The conclusion presents this as an empirical result rather than a formal guarantee.
  • Future work: For problems where models lack the required knowledge, instruction following and oracle conditioning alone may be insufficient, making explicit oracle-derived targets potentially necessary.The paper identifies memorization and pathological optimization as challenges in that regime.
  • Future work: The mechanism behind POPE’s exploration improvement remains an open theoretical question, including how to quantify and amplify instruction-following capabilities.The paper also highlights ray interference as a broader issue in heterogeneous prompt mixtures.

Appendices

The appendix analyzes how increasing the clip ratio can raise token entropy through optimistic updates on unlikely successful traces.

  • Clip-ratio analysis: Increasing the positive clip ratio can amplify entropy on hard problems by permitting optimistic updates on low-likelihood positive traces.The mechanism is especially relevant when the base model is unlikely to sample a successful trace.

B. Details of Pass@𝑘Policy Optimization

The section defines an unbiased pass@k objective and its policy-gradient estimator, then explains why optimizing it does not solve exploration on hard problems. It also connects POPE’s guided roll-ins to obtaining early non-zero rewards and transferring learning to unguided states.

  • Objective definition: Pass@k estimates the probability that at least one of k uniformly sampled rollouts is correct, increasing monotonically with observed successes and reducing to pass@1 when k=1.The estimator uses n≥k independent rollouts and c correct samples, then applies the objective per prompt across the training distribution.
  • Optimization: The pass@k objective can be optimized with standard RL by treating per-prompt estimator values as rewards and using an unbiased weighted policy-gradient update.The cited formulation defines correctness labels for sampled rollouts and weights the policy-gradient term with the unbiased pass@k estimator.
  • Exploration failure: Low-entropy initialization traps sparse-reward policies in locally consistent reasoning modes by concentrating updates on near-duplicate prefixes.Entropy collapse reduces exploration of alternative reasoning paths, making successful tail trajectories less likely to be sampled.
  • POPE intuition: POPE uses guidance as a roll-in distribution that reaches reward-bearing states, allowing early non-zero rewards and effective learning signals.The approach reframes exploration as reaching any state from which reward is attainable rather than improving behavior only after entering that region.
  • Transfer mechanism: Guided reasoning can transfer to unguided prompts because overlapping internal states let function approximation generalize from guided successes to nearby reachable prefixes.Self-verification, restarting, and backtracking create latent-state overlap even when training uses a fixed guidance segment.

E. Training Hyperparameters

The implementation uses full-parameter SFT and distributed GRPO-based RL with Pipeline-RL, starting from Qwen3-4B-Instruct and coordinating rollout, preprocessing, buffering, and optimization workers.

  • SFT configuration: All models start from Qwen3-4B-Instruct, with SFT using full-parameter fine-tuning, bfloat16 precision, and gradient checkpointing.SFT is implemented with the TRL codebase.
  • RL configuration: RL uses GRPO within Pipeline-RL, whose pipeline separates rollout generation, sample preprocessing, and policy optimization across worker types.Actors generate rollouts, preprocessing workers chunk and filter samples, and learner workers perform optimization.
  • RL configuration: Actors generate up to 8 rollouts per prompt, while a 128-capacity ring buffer replaces stale data when training lags behind generation.These settings coordinate asynchronous rollout production and learner consumption.
  • Reported settings: The appendix includes separate hyperparameter tables for SFT and RL training with GRPO under Pipeline-RL.The cited table captions identify the two configuration summaries but do not enumerate their values.

F. Qualitative Example

This qualitative example contrasts unguided reasoning with a partial human-written solution used as POPE guidance on a cyclic inequality problem. The example highlights how guidance supplies a constructive line of attack that unguided reasoning does not initially establish.

  • Setup: The example presents an original problem together with a partial human-written solution used as training guidance.The problem asks for the minimal λ satisfying a cyclic inequality for positive reals under n≥4k.
  • Partial oracle solution: The guided solution begins by defining the target sum and interpreting λ(n,k) as its maximum, then constructs a sequence to establish a lower bound.It sets a_i=x^{i−1} for small positive x while respecting cyclic indexing.
  • Evaluation condition: During evaluation, the model receives neither guidance nor a partial oracle solution, isolating the unguided behavior shown in the example.This distinguishes the training-time guidance condition from the evaluation condition.
  • Partial oracle solution: The cyclic structure creates a trade-off because each a_j appears in multiple denominators, so enlarging one term affects other terms.This motivates considering extremal or periodic constructions rather than optimizing terms independently.
  • Unguided solution: The unguided example shows a model trained with modified instructions attempting symmetry and Cauchy–Schwarz arguments without immediately obtaining a tighter extremal characterization.The default-instruction solution is separately identified, and evaluation provides no guidance or partial oracle solution.

G. More Examples

The additional examples illustrate POPE’s use of human- or model-generated solution prefixes across different mathematical problems. They include a set-construction problem and a prime-factor problem with detailed candidate elimination and verification.

  • Set-construction example: A set-construction example asks for the smallest n≥k+1 allowing each element to be represented as a sum of k other distinct elements.The example introduces a construction with k+1 base elements and four additional elements, targeting n=k+4.
  • Set-construction example: The proposed construction uses elements a_1,…,a_{k+1} and b_1,…,b_4, then verifies representations for both groups.The described verification checks that each constructed element can be expressed using k distinct others.
  • Set-construction example: The example concludes that smaller configurations fail because they lack enough elements to satisfy the representation conditions.The passage frames this as the reason testing smaller n does not produce valid configurations.
  • Prime-factor example: A DAPO example asks for the smallest natural n such that n^2−n+11 has exactly four prime factors, counting multiplicity.The supplied solution denotes the expression by f(n) and analyzes its possible small prime divisors.
  • Prime-factor example: The prime-factor solution rules out 4 factors at 11^4 because the resulting quadratic equation has no integer solution, then tests the next candidate 11^3×13.The discriminant for f(n)=14641 is not a perfect square, whereas the next candidate yields a square discriminant.
  • Prime-factor example: The solution verifies n=132 by computing f(132)=17303=11^3×13 and argues minimality using monotonicity and the absence of a smaller valid four-factor value.It identifies 11^4=14641 as the smallest ruled-out candidate below 17303.
Loading 2601.18779v1…