PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectives

Wei Xiong, Chenlu Ye, Baohao Liao, Hanze Dong, Xinxing Xu, Christof Monz, Jiang Bian, Nan Jiang, Tong Zhang

arXiv:2510.04996v3cs.LGcs.AIcs.CLstat.ML

TL;DR

Small-group uniform sampling can hide learning signals for difficult prompts, creating a signal-loss problem in RL for LLM reasoning. Reinforce-Ada uses a non-linear objective to guide adaptive allocation toward difficult prompts; across multiple LLMs and benchmarks, it improves signal quality and sample efficiency.

  • Problem

    Estimating gradients requires multiple responses per prompt, but small groups yield noisy estimates while large groups make inference costly.

    Source: §1 · p. 2

  • Method

    Reinforce-Ada uses a non-linear objective whose prompt-dependent gradient weights can be implemented by adaptively allocating response samples according to prompt difficulty.

    Source: §1 · p. 3

  • Results

    Across multiple LLMs and benchmarks, Reinforce-Ada improves signal quality and sample efficiency, achieving the benefits of large-n training at a fraction of its cost.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Reinforce-Ada is a plug-and-play replacement for the generation step in standard RL pipelines and requires no architectural modifications.

    Source: §1 · p. 3

    Experiments are restricted to the math domain due to resource constraints.

    Source: §6 · p. 17

Abstract

from arXiv · show

Reinforcement learning (RL) for large language model reasoning is frequently hindered by signal loss, a phenomenon where standard uniform sampling with small group sizes fails to uncover informative learning signals for difficult prompts. We demonstrate that this collapse is a statistical artifact of undersampling rather than an inherent model limitation. To address this systematically, we introduce a theoretical framework based on optimizing a non-linear RL objective (e.g., log-likelihood). We show that this objective naturally induces a weighted gradient estimator that prioritizes difficult prompts, which can be robustly realized through adaptive sampling. Guided by this framework, we propose Reinforce-Ada, a family of algorithms that dynamically allocates inference budgets based on prompt difficulty, effectively scaling up RL compute to where it is needed most. Unlike passive filtering methods that discard low-signal prompts, Reinforce-Ada actively invests compute to recover them. We introduce two efficient realizations: an estimation-based approach and a model-free sequential sampling approach. Extensive experiments across multiple benchmarks show that Reinforce-Ada significantly outperforms uniform baselines like GRPO, recovering lost signals and accelerating convergence by up to $2\times$ while maintaining the same total inference budget. Code is available at https://github.com/RLHFlow/Reinforce-Ada.

1 Introduction

Small response groups can erase useful learning signals even when prompts have non-trivial success probabilities. Reinforce-Ada addresses this undersampling problem by weighting difficult prompts through adaptive allocation of inference budgets.

1 Introduction

  • With small groups, identical rewards make GRPO advantages and gradients vanish; this occurs for difficult prompts early and trivial prompts later.Finite-sample fluctuations can hide the true signal, while reliably using larger groups incurs unsustainable inference cost.Source: §1 · p. 2
  • 26.5% at pass@1 rises to 81.3% at pass@256, while all-correct groups fall from 35.3% at n=4 to 10.2% at n=256.These Open-R1 results show that larger groups can recover signals hidden by small samples.Source: §1 · p. 2, Figure 2 · p. 3
  • A non-linear objective such as log-likelihood weights gradients toward low-pass-rate prompts, and adaptive sampling realizes this weighting by allocating them more responses.For the log objective, the prompt-dependent weight is 1/p.Source: §1 · p. 3
  • Reinforce-Ada offers estimation-based allocation using online pass-rate estimates and sequential allocation that samples until sufficient positive responses are collected.The sequential approach is model-free and avoids explicit pass-rate estimation.Source: §1 · p. 3
  • Across multiple LLMs and benchmarks, Reinforce-Ada improves signal quality and sample efficiency, achieving large-n training benefits at a fraction of the cost.It replaces the generation step in standard RL pipelines without architectural modifications.Source: §1 · p. 3

2 The Weighted Objective Framework

Uniform small groups can lose learning signals, while passive filtering wastes generated responses and may exclude difficult prompts. The framework instead uses a non-linear objective whose prompt-dependent gradient weights motivate adaptive sampling.

2.1 Prior Approach: Passive Filtering and Large Group Size

  • Passive filtering discards uniform-reward groups after paying to generate them, while large uniform groups recover signals at computationally prohibitive cost.Discarding difficult prompts can prevent learning on them; adaptive allocation is proposed to spend more inference where signals are scarce.Source: §2.1 · p. 4

2.2 A Principled Solution: The Weighted Objective Framework

  • A non-linear transformation of prompt pass rates assigns higher marginal utility to improvements on low-pass-rate prompts and induces a prompt-dependent gradient weight.The framework includes the standard objective when f(p) = p.Source: §2.2 · p. 4
  • For the log-likelihood objective, the weight is 1/p, prioritizing difficult prompts as their pass rates approach zero.Concave functions such as log(t) and t assign larger weights to difficult prompts.Source: §2.2 · pp. 4–5, Figure 3 · p. 5
  • Explicit weighting can fail when a small group estimates a difficult prompt’s pass rate as zero, whereas implicit weighting allocates variable group sizes in proportion to the prompt weight.The implicit strategy absorbs the weight into prompt sampling rather than multiplying the gradient by it.Source: §2.2 · p. 5
  • A hybrid log-objective strategy allocates samples proportional to 1/√p and applies a residual 1/√p gradient weight to divide variance across two stages.The text describes this balance as a way to avoid allocating excessive compute to the hardest prompts.Source: §2.2 · p. 6
  • The framework connects prompt-dependent weighting to GRPO and identifies the log-objective as optimal for variance reduction under a fixed inference budget.The paper also states that it generalizes prior findings from rejection-sampling fine-tuning to the general REINFORCE algorithm.Source: §2.2 · p. 6

3 Reinforce-Ada: Reinforce with Adaptive Sampling

Reinforce-Ada estimates prompt difficulty or samples sequentially until enough successes are collected, allocating more inference to prompts with scarce signals. Its sequential method also compares with DAPO’s fixed-group filtering and describes a static-batch implementation.

3.1 Reinforce-Ada-Est: Estimation-based Allocation

  • For Reinforce-Ada-Est, the log-objective’s target allocation is proportional to 1/p, while the implemented hybrid allocates samples proportional to 1/√p and applies another 1/√p weight.Ada-EMA tracks prompt-level success with decayed historical counts and a Bayesian prior, keeping estimates non-zero after batches with no successes.Source: §3.1 · pp. 6–7
  • Online pass-rate estimates guide Reinforce-Ada-Est’s adaptive budgets, avoiding a separate exploration phase that can estimate difficult prompts as zero and discard them.Estimates can come from a value network or historical training data; the estimator need only capture relative prompt difficulty.Source: §3.1 · p. 6
  • Estimation-based allocation may require auxiliary-network overhead or persistent statistics and repeated prompts, which may not suit every training setup.The paper presents these as implementation requirements of the estimation-based strategies.Source: §3.2 · p. 7

3.2 Reinforce-Ada-Seq: Implicit Allocation via Sequential Sampling

  • Reinforce-Ada-Seq samples until a fixed number of correct responses is collected, yielding an expected sample count of 1/p without estimating p beforehand.The paper generalizes this sample-until-condition idea to sequential rounds over a batch of prompts.Source: §3.2 · pp. 7–8
  • Sequential sampling removes prompts when they meet positive-focused or balanced correct-and-incorrect response thresholds, with rounds capped by a maximum budget.The balanced condition gathers both correct and incorrect cases; an explored within-round pass-rate allocation showed no clear gains over the simpler version.Source: §3.2 · p. 8
  • Oversample-downsample-correct converts variable response pools into static training batches, using a high-fidelity baseline and explicit weighting after downsampling.The downsampled group is fixed-size, and the gradient weight 1/p̂ restores the weight removed with the sequential sample count.Source: §3.2 · p. 9

3.3 Comparison with the Dynamic Sampling in DAPO

  • Unlike DAPO’s fixed-group discarding, Reinforce-Ada reallocates compute within prompts to obtain signals on difficult prompts; the approaches can be combined.The paper argues DAPO may discard both difficult prompts and very easy prompts, biasing training toward mid-difficulty problems.Source: §3.3 · p. 10

4 Experiment

Experiments compare adaptive sampling with fixed-size GRPO across math models and benchmarks, examining accuracy, compute costs, learning dynamics, reward–entropy trade-offs, and Pass@k.

4.1 Experimental Setup

  • Experiments use four math-oriented LLMs, standard OpenR1-Math-220k training data, and MATH500, Minerva Math, OlympiadBench, and a 230-problem competition set.GRPO uses fixed groups of n = 4, 8, or 16; Seq adaptively samples up to 32 responses and downsamples to n = 4 for updates.Source: §4.1 · pp. 10–11

4.2 Main Result

  • 47.6% vs. 47.3%: Seq-Balance matches or exceeds GRPO-n16 on Qwen2.5-Math-1.5B with inference comparable to n ≈8−10 and update cost n = 4.Figure 4 reports faster learning and higher reward than GRPO across backbones, with Balance typically reaching the highest asymptote.Source: §4.2 · p. 12, Figure 4 · p. 12
  • Adaptive sampling generally beats passive filtering, while Seq-Balance outperforms Seq-Pos by continuing to collect rare errors and preserve gradient variance.DAPO improves over GRPO-n4 (45.9% vs 45.3%) but generally trails adaptive methods; Ada-Est and Ada-Seq are not directly comparable because their costs differ.Source: §4.1 · p. 11, §4.2 · p. 12

4.3 Analysis of Efficiency and Learning Dynamics

  • GRPO-n4 < Seq-Pos < Seq-Balance < GRPO-n16 in inference cost, while Ada-Est leads the reported performance ranking and uses less compute than GRPO-n16.Seq-Balance's inference cost rises after about 300 steps as it searches for rare negative responses; on the 1.5B model, Seq-Pos and Seq-Balance increase step time by about 2.2× and 2.8×.Source: §4.3 · pp. 13–14

4.4 Entropy Dynamic and Pass@k

  • Reinforce-Ada shifts the reward–entropy frontier outward and yields the strongest Pass@k gains at practical budgets k ≤8, with Seq-Balance typically best.The advantage narrows as k grows; Seq-Balance typically remains marginally best in that diminishing-returns regime.Source: §4.4 · p. 15

5 Related Work

Related work addresses uniform-reward signal loss through filtering, altered advantages, prompt selection, or weighted objectives. Reinforce-Ada instead adaptively gathers responses and connects nonlinear objectives to adaptive sampling.

Data filtering and selection in online RL training for LLMs

  • Earlier data-selection methods oversample responses and downsample by reward variance, process rewards, tool validity, or trajectory search.These methods select from generated responses, whereas Reinforce-Ada adapts sampling to gather signal during collection.Source: §5 · pp. 15–16

Addressing signal loss in GRPO

  • Prior approaches filter uniform-reward groups, alter advantage computation, or select prompts; Reinforce-Ada instead gathers sufficient signal adaptively at response collection.Filtering may discard difficult prompts lacking positive responses, while this approach allocates compute to recover their latent learning signals.Source: §5 · p. 16

Learning objective in RLVR

  • Yao et al. (2025) connect EM-RAFT gradients and optimal sampling budgets to 1/pθ(x); this work extends the analysis to the log-objective for standard Reinforce.The paper frames explicit weighting and implicit adaptive sampling as dual ways to optimize the nonlinear objective.Source: §5 · pp. 16–17
  • Reinforce-Ada adds estimation-based and model-free sequential realizations; its adaptive sampling is complementary to policy-gradient update-rule modifications.The paper distinguishes its practical algorithmic contribution from concurrent theoretical work by Davis & Recht (2025).Source: §5 · p. 17

6 Discussion and End Note

Reinforce-Ada uses adaptive sampling to recover learning signals by allocating inference according to prompt difficulty. The authors distinguish response-level sampling from prompt-level data curation and note that experiments are limited to math.

6 Discussion and End Note

  • The authors present Reinforce-Ada as a lightweight training-loop replacement that improves convergence and final performance with moderate computational overhead.They frame it as a theoretically grounded alternative to uniformly large groups.Source: §6 · p. 17
  • The experiments are restricted to math because of resource constraints, and the authors note that prompt-set difficulty evolves during training.They position adaptive sampling as a response-level building block within broader data curation across the post-training pipeline.Source: §6 · p. 17

A Authorship and Credit Attribution

  • WX and CY developed core project ideas and sequential sampling; HD coordinated the project and production implementation, while BL contributed data, experiments, and released code.XX, CM, JB, NJ, and TZ served as senior authors, advising the work, providing resources, and suggesting experiments and writing improvements.Source: A Authorship and Credit Attribution · p. 22

B Variance-Reduction Gradient Estimator under the Log-objective

This section extends prior analysis of the log-objective from rejection-sampling fine-tuning to the general Reinforce algorithm with a baseline. It connects the framework to variance reduction.

B Variance-Reduction Gradient Estimator under the Log-objective

B.1 Optimal Budget Allocation

For the log-objective, the section treats sample allocation as a variance-minimization problem for estimating the batch gradient. Its optimal-allocation reasoning depends on assumptions about prompt gradients and on the objective’s weighting.

B.1 Optimal Budget Allocation

  • For any allocation with at least one sample per prompt, the estimator remains unbiased; sample counts are chosen to minimize total gradient variance.The derivation assumes similar gradient norms across prompts.Source: §B.1 · pp. 22–23
  • Adding a baseline reduces gradient variance and changes the optimal sampling strategy; the analysis relates this to GRPO’s group-standard-deviation normalization (Shao et al., 2024).For binary rewards, the standard deviation is tied to p(1 − p).Source: §B.1 · pp. 23–24
  • The log-objective’s 1/p weighting is essential for directing variance-reduction effort toward difficult prompts; the standard objective instead favors prompts near p = 0.5.The log-objective allocation concerns variance reduction, not a change to the optimization objective through sample counts.Source: §B.1 · pp. 22, 24

C.1 Adaptive Sampling Solves More Difficult Prompts

Adaptive sampling’s advantage over uniform GRPO is more pronounced on challenging prompts. Reinforce-Ada-Seq-Balance improves accuracy across difficulty groups, including prompts that the base model rarely solves.

C.1 Adaptive Sampling Solves More Difficult Prompts

  • On the hard subset, selected for 1–2 correct responses out of 16 initially, adaptive sampling widened its margin over GRPO late in training; Figure 8 shows a larger benefit on challenging than moderate prompts.After about 200 steps, most prompts were easy enough that two rounds met the positive quota.Source: §C.1 · p. 24, Figure 8 · p. 25
  • By +36.74 and +39.37 points on Extremely Hard and Hard prompts, respectively, Reinforce-Ada-Seq-Balance improved over the base model and led RL methods across difficulty levels (Easy: 71.53%).DAPO even hurts performance on Easy prompts.Source: Table 5 · p. 25, §C.1 · p. 25
  • Among 5,000 hard-set prompts, 19.7% were extremely hard and 61.7% hard; base accuracy across extremely hard, hard, medium, and easy groups was 0.00%, 8.89%, 29.50%, and 61.51%.Difficulty groups were defined using the base model’s pass@16.Source: §C.1 · pp. 24–25

C.2 Variants of Reinforce-Ada-Est

The comparison of sampling and reweighting strategies finds similar prompt-level reward for the hybrid and implicit-weighting approaches, but a declining batch-level reward under implicit weighting. This pattern is linked to difficult prompts receiving too many draws and simpler prompts too few.

C.2 Variants of Reinforce-Ada-Est

  • Implicit weighting keeps prompt-level reward similar to the hybrid strategy, but its batch-level reward eventually decreases.The authors attribute the decline to excessive sampling of negative responses and difficult prompts.Source: §C.2 · p. 25
  • A large prompt-to-batch reward gap signals negative covariance between prompt draws and rewards, with low-reward prompts dominating the budget.Under finite sampling, the authors recommend broad prompt coverage and more moderate sampling to avoid imbalance.Source: §C.2 · p. 26
  • Figure 9 compares different sampling and reweighting strategies.Source: Figure 9 · p. 26

D Simulation of Sampling Cost of Reinforce-Ada-Seq

The simulation estimates sampling costs for two Reinforce-Ada-Seq stopping rules across success probabilities and exploration budgets. It varies the stopping requirement and reports expected sample counts.

D Simulation of Sampling Cost of Reinforce-Ada-Seq

  • Reinforce-Ada-Seq-pos stops after K positive responses, while Reinforce-Ada-Seq-balance stops after collecting K positive and K negative responses.Source: D Simulation of Sampling Cost of… · p. 26
  • The simulations vary K and true success probability p for maximum exploration budgets Nmax of 32, 64, and 128, with kbatch = Nmax/8.Expected required sample counts are estimated; responses are modeled as Bernoulli trials.Source: D Simulation of Sampling Cost of… · p. 26
  • Figure 10 reports expected response counts for the two stopping requirements, with columns for Nmax values 32, 64, and 128.Source: Figure 10 · p. 27

Related papers

Loading 2510.04996v3…