Recover learning signals in RL for LLM reasoning by dynamically allocating sampling budget based on prompt difficulty. Use log-objective weighting (1/p for pass rate p) to prioritize challenging examples, achieving 2x convergence speedup versus uniform sampling while maintaining identical compute budgets across math, coding, and general benchmarks.
Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectives
version
0.0.2
engine
skillxiv-v0.0.2-claude-opus-4.6
license
MIT
url
https://arxiv.org/abs/2510.04996
keywords
["adaptive sampling","non-linear RL","gradient estimation","RL for reasoning","signal recovery"]
description
Recover learning signals in RL for LLM reasoning by dynamically allocating sampling budget based on prompt difficulty. Use log-objective weighting (1/p for pass rate p) to prioritize challenging examples, achieving 2x convergence speedup versus uniform sampling while maintaining identical compute budgets across math, coding, and general benchmarks.
Reinforce-Ada: Adaptive Sampling Framework for Non-Linear RL Objectives
Core Concept
Standard group-based RL (GRPO) suffers signal loss when small groups produce identical rewards—advantages normalize to zero, causing gradient collapse. The root cause is undersampling difficult prompts, not model limitations. Reinforce-Ada recovers learning signals by dynamically allocating more samples to harder prompts, weighted by an implicit importance function derived from optimizing non-linear reward objectives.
Architecture Overview
Non-Linear Objective Optimization: Frame RL as maximizing f(p_θ(x)) where f is log, power, or other monotonic function and p_θ(x) is per-prompt pass rate
Implicit Weighting: Optimal gradient estimator naturally prioritizes difficult prompts with weight proportional to f'(p)
Two Implementation Strategies: (1) Estimation-based: explicit reweighting with value network estimates; (2) Sequential: successive elimination of solved prompts
Budget Efficiency: Allocate inference compute dynamically rather than uniformly across all prompts
Implementation Steps
1. Problem Formulation and Theoretical Framework
Define weighted RL objective:
J_f(θ) = E_x[f(p_θ(x))]
where f is a non-linear function of per-prompt pass rate. The gradient naturally acquires prompt-dependent weights:
Signal Loss Root Cause: When all group members get identical rewards, standardized advantages collapse to zero. This is statistical undersampling, not model failure—fix by allocating more samples to difficult prompts.
Weighting Strategy: Log-objective (weight = 1/p) is both theoretically variance-optimal and empirically robust. Power functions (p^α) offer softer weighting if needed.
Algorithm Selection: Ada-Seq (successive elimination) avoids requiring value network estimates and is model-free. Ada-Est scales better for very large prompt sets but requires training value network.
Convergence: Expect 2× faster convergence to comparable performance using identical total compute. Wall-clock overhead: 1.3-2.8× depending on implementation, but offset by training speedup.
When to Use / When NOT to Use
Use When:
Training reasoning models (math, coding, STEM) with verifiable rewards
Small-to-medium group sizes (n=4-8) causing gradient collapse in GRPO
You have computational budget for adaptive allocation (1.3-2.8× overhead acceptable)
Task difficulty varies substantially across examples
NOT For:
When all examples have similar difficulty (uniform sampling sufficient)
Very large-scale distributed training where centralized difficulty tracking is infeasible
Tasks where pass rate estimation is unreliable or undefined
Reference
This skill encodes techniques from "Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectives" (arXiv:2510.04996). Code available at https://github.com/RLHFlow/Reinforce-Ada.
