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
cs.LG, cs.AI, cs.CL, stat.ML
2025-10-07
GRPO's small groups often yield zero gradients. Reinforce-Ada spends extra rollouts on hard prompts; Seq-Balance hits 47.6% on 1.5B, matching GRPO-n16 at 47.3% with an n=4 update.
RL with verifiable rewards for LLM reasoning usually runs GRPO: draw a fixed n responses per prompt and normalize advantages inside the group. Small n makes hard prompts land all-wrong and easy ones all-correct, so group variance hits zero and the gradient vanishes. On an Open-R1 subset, Qwen2.5-Math-1.5B scores 26.5% pass@1 but 81.3% pass@256. With n=4, 35.3% of prompts are all-correct; at n=256 that share falls to 10.2%. The signal is often there. Uniform undersampling hides it.
Prior fixes are mostly passive. DAPO drops zero-variance groups and redraws prompts. Others raise n uniformly to 16 or even 512. Dropping never trains the hardest items. Uniform large n wastes rollouts on easy ones. The bet here is to keep a similar total budget and spend the extra samples where the group still has no mixed outcomes.
The usual objective sums pass rates p with weight 1. A nonlinear objective such as log p puts a 1/p factor on the gradient, so hard prompts count more. That weight can multiply the gradient explicitly, or it can become extra samples on hard prompts. Explicit weighting does not fix all-zero groups: if the Monte Carlo estimate of p is already 0, scaling it still yields 0. Adaptive sampling is the actual lever.
Reinforce-Ada-Est estimates p online with a value net or a decayed Bayesian moving average, allocates rollouts proportional to 1/√p, and applies another 1/√p residual weight at update time. Splitting the log objective across sampling and the gradient keeps the hardest prompts from monopolizing compute.
Reinforce-Ada-Seq never estimates p. It samples in rounds, generating M more responses for still-active prompts until an exit rule or a cap. Seq-pos stops after enough correct answers; Seq-balance also demands enough incorrect ones. Sampling until a fixed number of positives has expectation 1/p, which matches the log objective. In practice the variable pool is downsampled to a static n=4 update group, and the full-pool mean is used as a high-fidelity baseline so the GPU graph stays static.
DAPO keeps n fixed, so hard prompts are statistically destined to look empty and get dropped. Ada spends more rollouts inside the same prompt until a rare success appears.
Four backbones, math benchmarks (MATH500, Minerva, OlympiadBench, a 230-problem AIME-like set), Ave@32. Update groups are n=4. Seq may draw up to 32 then downsample.
| Model | Method | Weighted average |
| Qwen2.5-Math-1.5B | GRPO-n4 / n8 / n16 | 45.3 / 46.1 / 47.3 |
| same | DAPO | 45.9 |
| same | Seq-pos / Seq-balance / Est | 46.1 / 47.6 / 46.5 |
| Qwen2.5-Math-7B | GRPO / Seq-balance | 53.3 / 54.6 |
| Llama-3.2-3B-Instruct | GRPO / Seq-balance | 27.9 / 29.1 |
| Qwen3-4B-Instruct | GRPO / Seq-balance | 66.5 / 67.6 |
On the 1.5B model, Seq-balance reaches 77.4 on MATH500 versus 76.9 for GRPO-n16. Reward curves rise faster and plateau higher. Seq-pos exits early once positives are cheap, and later looks like uniform sampling. Seq-balance starts hunting hard negatives, so its cost curve is U-shaped and group variance survives.
Wall-clock is not free. On 1.5B with 8×H100, GRPO takes 102 s/step, Seq-pos 228 s (2.2×), Seq-balance 290 s (2.8×), Est 128 s (1.3×). Relative overhead shrinks on 7B (Seq-balance 1.59×), because positives appear quickly and the 7B step is dominated by the backward pass. The abstract's "up to 2× faster convergence" is reward versus steps, not wall-clock. Backward cost matches GRPO-n4; the extra spend is inference.
On the reward–entropy frontier, raising GRPO's n does not push the curve out. Ada gets more reward at a given entropy and better pass@k at small k.
"No gradient on hard prompts" is often read as "the model cannot solve them." Here it is undersampling. The implementation is a drop-in generation API in verl, no architecture change. For teams already running GRPO, Seq-balance buys n=16-like signal quality at roughly n=8–10 inference and an n=4 update.
This is micro-allocation inside a prompt, not a curriculum that swaps prompts. The authors note it can stack with DAPO-style batch filling.
Gains are incremental: 45.3 to 47.6 on 1.5B, 53.3 to 54.6 on 7B. Useful, not a new capability tier.
Experiments are math-only with verifiable rewards; the authors say compute limited them, and real post-training needs the whole data pipeline. Seq waits synchronously on the slowest sample; async would be faster and is not tested. Est and Seq do not share inference or training cost, so variant rankings are not a clean ablation.
Prompts that were all-wrong or too easy under 16 base samples were filtered before training, so the method is tested on a moderate-difficulty slice, not on impossible items from scratch. Runs last 600 steps with GRPO hyperparameters left untouched. That is a fair comparison and may also understate a tuned ceiling. The log objective has unbounded weight as p→0; Nmin/Nmax and the 1/√p hybrid are engineering clamps, so theory and code still have a gap.