Predicting Which Prompts Are Worth Sampling: State-Dependent Noise Filters for Rollout Allocation in GRPO

Reinforcement learning on language models spends most of its time generating text. Group Relative Policy Optimization (GRPO) is the standard example. It is a critic-free method that samples a group of responses for each prompt and scores each response against the group's average reward. When every response in a group is right, or every one is wrong, the group teaches the model nothing, and all the compute spent decoding it is wasted. Current fixes fall into two kinds. Some detect the waste after generation and patch the gradient. Others spend a small "probe" batch of generations to estimate how hard a prompt is. Both treat each prompt's success rate either as unknown until it is sampled or as a quantity whose uncertainty evolves the same way for every prompt.

We propose to treat each prompt's success probability as a hidden state that drifts as the policy trains, and to track it with a filter whose noise depends on the prompt. A small head on the policy's prompt encoding supplies two things for each prompt: a prior guess of its success rate, and how fast that rate is likely to change. Past rollouts then update the estimate. Its observation noise is set by the binomial variance $p(1-p)/n$, so it is state-dependent by construction. The filtered belief is then used before any decoding happens. It decides how many rollouts each prompt gets, or whether it gets any, so that the batch of prompts is expected to carry as much nonzero-advantage signal as possible. The aim is to keep the generation savings of probe-based allocation while dropping the probe stage, and to work from the first epoch on prompts the model has never seen.

Core Claim

Wasted rollouts in group-based RL come from mis-predicting each prompt's reward variance before sampling. The relevant noise is heteroscedastic, meaning it differs from prompt to prompt, in two ways. The first is observation noise: binary rewards have variance $p(1-p)$, which shrinks near easy and impossible prompts. This is exactly the "U-shaped" collapse pattern reported in Advantage Collapse in Group Relative Policy Optimization. The second is process noise: prompts near the policy's capability frontier change success rate quickly during training, while saturated or hopeless prompts barely move. A filter that models both per prompt should allocate generation compute better than three alternatives. The first is a fixed group size. The second is a filter with global constant noise, as in Kalman Filter Enhanced GRPO, whose authors explicitly leave adaptive process and measurement noise as future work. The third is a probe-then-allocate scheme with an unconditioned Beta-Binomial posterior, as in AERO from Train Less, Learn More.

Research Program

Let $z_{i,t}$ be the log-odds of prompt $i$ being solved by the policy at training step $t$, with success probability $p_{i,t} = \sigma(z_{i,t})$, where $\sigma$ is the logistic function. We model

$$z_{i,t+1} = z_{i,t} + w_{i,t}, \quad w_{i,t} \sim \mathcal{N}(0, Q_\phi(x_i, t)), \qquad k_{i,t} \sim \mathrm{Binomial}(n_{i,t}, p_{i,t}).$$

Here $x_i$ is the prompt and $Q_\phi$ is the prompt-dependent process noise predicted by a small head with parameters $\phi$. The term $k_{i,t}$ counts successes among the $n_{i,t}$ rollouts actually drawn. The same head predicts a prior mean and variance for $z_{i,0}$ for prompts that have never been sampled. The head reads the policy's last-layer prompt representation, which the policy computes anyway during prefill, the parallel pass over the prompt before decoding begins. We update the binomial likelihood with a Laplace (Gaussian-approximation) step, which gives a per-prompt posterior mean $\hat z_i$ and variance $P_i$ at the cost of a scalar operation per prompt.

The head is fit online by maximum likelihood on the observed success counts. Training data come free from the rollouts already generated for the policy update. This is the same decoupling of mean from variance that chained Gaussian processes use in Extending Model-based Policy Gradients for Robots in Heteroscedastic Environments. There, one latent process models the signal and a second models the log-variance. We borrow that structure but replace the Gaussian process with a linear or two-layer head, so cost does not grow cubically with the number of prompts seen.

Allocation uses the posterior directly. A group of size $n$ yields a nonzero GRPO gradient with probability $1 - p^n - (1-p)^n$. We integrate this over the filter's belief and choose integer group sizes $n_i \in \{0, 2, 4, \dots, n_{\max}\}$. The objective is to maximize the expected number of informative groups, weighted by the expected advantage magnitude $\sqrt{p(1-p)}$, under a fixed per-step token budget. A greedy marginal-gain solver suffices because the objective is concave in $n$.

High posterior variance $P_i$ raises the value of sampling a prompt, since its outcome is uncertain. Allocation therefore explores prompts whose difficulty is unknown instead of skipping them. This is the specific advantage over hard thresholding. The posterior mean can also replace the group mean as the advantage baseline, which gives a per-prompt, state-dependent version of KRPO's normalization. We treat that as a secondary output, not the main contribution.

Baselines

The naive reference is vanilla GRPO with a fixed group size of 8 or 16 for every prompt. This is the cost the field is trying to reduce. It is run on the same prompts, model, and number of optimizer steps, and is reported both at equal steps and at equal generated tokens.

The strongest existing competitor is AERO from Train Less, Learn More. It spends a probe budget, updates a Beta-Binomial posterior per query, and rejection-samples to a 1:1 correct-to-incorrect ratio. It reports reducing total training compute by "about 48%" and per-step wall-clock time by "about 45% on average", reaching "~48% Avg@8" on Qwen2.5-7B with less compute than GRPO. It is the right opponent because it targets the same waste with the same tools: Bayesian success-rate posteriors and adaptive group sizes. We will run it from its released recipe on its own OpenR1-AERO math data with identical models, token budget, and tuning budget for the rescue threshold. We will spend the same number of tuning runs on our head's learning rate and budget. Beating it means matching its Avg@8 at strictly fewer generated tokens, or exceeding it at equal tokens, with lower step wall-clock time once probe calls are counted.

The third baseline is a history-only tracker. It keeps each prompt's last observed pass rate and skips prompts whose last group was all-correct or all-wrong, similar in spirit to the zero-variance elimination used in Each Prompt Matters. We have no standalone reported number on Lacuna for this component in isolation; that paper reports a combined "1.66x overall speedup" for its full system.

Ablations isolate the key ingredient. One fixes $Q$ to a global constant fit on held-out data, which is the KRPO-style homoscedastic filter. A second removes the prompt-conditioned prior, so unseen prompts start from a flat belief. A third removes the filter and uses only the head's prediction. If the homoscedastic-$Q$ ablation matches the full method, the state-dependent part is not earning its keep and we will say so.

Why not just…?

Why not just remember each prompt's last pass rate and skip saturated ones? This is the most serious threat. In multi-epoch training on a small dataset it may capture most of the gain. It fails in two regimes our experiments target. In the first epoch, or on streaming data, there is no history. And on prompts near the capability frontier, a stale all-wrong group from several hundred steps ago is precisely the prompt that has since become learnable. The prompt-dependent process noise exists to let those prompts re-enter. We will report the history baseline separately on first-epoch steps and on frontier prompts, the ones whose eventual pass rate exceeds their initial rate. If the history baseline ties the full method in both slices, we will report that the learned noise model is unnecessary.

Why not just use AERO's probe? The probe works, but it is a serial generation round before allocation, and it allocates from an unconditioned per-query Beta-Binomial that knows nothing about similar prompts. Our method reaches an allocation decision from prefill alone. The decisive comparison is wall-clock time per step including probe latency, plus accuracy at matched tokens. If AERO wins on accuracy at equal tokens, the probe's information outweighs our prediction. In that case we would test using our prior to size AERO's probe, rather than claiming replacement.

Why not just fix collapsed groups after the fact with virtual rewards or quantile baselines? AVSPO in Advantage Collapse in GRPO restores gradients with "<0.01% increase in training time". QAE in Quantile Advantage Estimation zeroes roughly 80% of advantages and lifts Qwen3-8B-Base AIME'24 pass@1 "from 39.69% to 48.23%". Neither saves any decoding: every rollout is generated before it is discarded or patched. The two approaches are orthogonal to ours, so we will also run our allocator combined with QAE to check that the savings compose.

Why not just train a critic and sample one response per prompt? Best Practice Critic Optimization shows a stabilized critic can match 16-sample GRPO with one response. The cost is keeping a full-size value network in memory and training it. Our head is a few thousand parameters on existing activations, and it predicts prompt-level outcome statistics rather than token-level values. We will report peak memory alongside accuracy so the trade-off is visible, not hidden.

Proposed Experiments

Training uses Qwen2.5-Math-1.5B and Qwen2.5-7B on the OpenR1-AERO math set and on DAPO-Math-17K. Evaluation covers AIME, AMC, MATH-500, MinervaMath, and OlympiadBench (codebase), with Prime-1.4K code problems as a second reward type where verifier latency makes skipping rollouts more valuable. The main metric is a curve of benchmark accuracy against cumulative generated tokens and against wall-clock time.

Mechanism metrics include the fraction of zero-variance groups per step, compared against the Advantage Collapse Rate that Advantage Collapse in GRPO reports cutting by "58–63%". We also measure calibration of predicted pass rates on held-out prompts, using Brier score and the binomial negative log-likelihood of the next group's outcome.

The decisive checks are three. First, the full method should beat the homoscedastic-$Q$ ablation in predictive likelihood, specifically on frontier prompts. Second, it should match AERO's Avg@8 at fewer generated tokens without a probe stage. Third, its advantage over the history baseline should be concentrated in first-epoch and frontier slices, not spread uniformly. If the first check fails, the state-dependent noise claim is false regardless of the end accuracy.