Training a language model with reinforcement learning against an automatic checker (a unit-test runner, a math answer matcher, a malware sandbox) is expensive. The model has to generate many attempts per problem, and the checker has to grade each one. Recent methods cut this cost by predicting, from past results, how often the model will solve each problem. They then spend attempts only where the outcome is uncertain, because problems the model always solves or always fails teach it nothing. These predictors assume that the stream of problems and the checker itself stay put. Security practitioners know that assumption breaks. Malware detectors trained on one year's apps lose most of their accuracy on later years, partly because the software ecosystem changes and partly because attackers deliberately make new samples look like old, easy ones.
This note proposes to treat the rollout budget as a target of drift, and in the adversarial case as a target of attack. A predictive allocator that is confidently wrong will starve exactly the problems that have just become informative. We will show this failure precisely, and correct it by spending a small, targeted probing budget wherever a cheap drift signal says the predictor has gone stale. We will test the correction with the train-on-the-past, test-on-the-future protocol that the malware community uses. The aim is to keep the cost savings of predictive allocation while matching the robustness of brute-force uniform sampling.
Core Claim
The setting is group-based reinforcement learning with verifiable rewards (RLVR). Here a binary correctness signal from a deterministic checker trains the model. The advantage of each attempt is computed relative to the other attempts on the same prompt, as in GRPO and RLOO, which avoids a separate critic network. Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards (VIP) shows that a prompt with success probability $p_i$ that receives $K_i$ attempts contributes gradient variance proportional to $p_i(1-p_i)/K_i$. VIP tracks $p_i$ with a Gaussian process over prompt embeddings and solves a convex allocation under a total budget. Its overhead is about 1% of training time. VIP explicitly treats the prompt distribution as stationary.
Our first claim is structural. Suppose the allocator has a posterior over $p_i$ with mean $\mu_i$ and variance $\sigma_i^2$. Then the expected learning signal is
$$\mathbb{E}[p_i(1-p_i)] = \mu_i(1-\mu_i) - \sigma_i^2 .$$
This follows directly from $\mathbb{E}[p^2]=\sigma^2+\mu^2$. Whether the allocator plugs in the posterior mean or averages over the posterior, uncertainty never earns a prompt more attempts. After a shift, the posterior mean for a drifted prompt is inherited from similar-looking old prompts and is often near 0 or 1. The allocator then gives that prompt the minimum, and the evidence that would correct the prediction never arrives. This is the rollout-budget analogue of the "confident error" that defeats uncertainty sampling on drifted malware.
The claim has a sharper adversarial version. An adversary that produces prompts close in embedding space to mastered ones but harder in fact can push compute away from the prompts that would teach the model most. Two examples are a problem-proposing model in the style of Better LLM Reasoning via Dual-Play, or the packing and obfuscation that malware authors use. The adversary does this without ever touching the gradient.
Our second claim is that a cheap fix exists and that it is not simply "forget faster." The allocation score adds the expected value of information to the variance term, but only inside regions a drift monitor has flagged. The monitor watches the gap between predicted and observed pass rates on the prompts that were actually sampled, aggregated over embedding neighborhoods. It borrows the idea of Combating Concept Drift with Explanatory Detection and Adaptation for Android Malware Classification (DREAM), which flags drift when its classifier's predictions shift, rather than relying on embedding novelty alone. Embedding novelty cannot see a surface-similar adversarial prompt. Prediction residuals can.
The same logic applies to the checker changing underneath the model. Concept shift in this setting means a previously correct answer becomes incorrect, for example because tests are tightened or a library function is deprecated. Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse (AR3PO) reuses past correct responses for unsolved prompts and assumes those responses stay correct. Our method re-runs the checker on a reused response only when its region is flagged. Each re-check costs one execution rather than a fresh group of generations.
Research Program
We will build three components on top of an RLOO training loop.
The first is the predictor: VIP's Gaussian process over prompt embeddings, kept as is so that differences are attributable to our changes.
The second is the drift monitor. It clusters prompt embeddings into neighborhoods and keeps a running cumulative-sum statistic of standardized residuals between predicted and observed pass rates in each neighborhood. When the statistic crosses a threshold, it raises the Gaussian process variance for that neighborhood. The threshold is set to a fixed false-alarm rate on a stationary held-out run.
The third is the allocator. It maximizes the sum of $\mu_i(1-\mu_i)/K_i$ plus $\lambda$ times the expected reduction in $\sigma_i^2$ from probing, restricted to flagged neighborhoods. All of this is subject to a single budget that counts probes, re-verifications, and training rollouts together. Counting every attempt against the same budget is what makes the comparison with uniform sampling honest.
The analysis has two strands. On the theory side, we will bound how many steps a drifted prompt goes unsampled under plug-in allocation, as a function of how far its true $p$ has moved from the predicted one. We will then show that the information term caps this delay. On the measurement side, we introduce a "starvation rate." It is the fraction of prompts whose true pass rate, estimated offline with 64 attempts, lies between 0.2 and 0.8 but which received the minimum allocation in a training step. Alongside it we measure recovery time: the number of steps after a shift until allocation on the shifted region returns to its oracle level.
Of the three directions, the computational cost of reinforcement learning is the core mechanism here. Verifiable rewards are what make the predicted pass rate meaningful in the first place. Adversarial drift supplies both the stress test and the evaluation protocol. That protocol comes from LAMDA: A Longitudinal Android Malware Benchmark for Concept Drift Analysis, which reports performance on chronologically later data rather than random splits, and from DRMD's area-under-time metric. DRMD: Deep Reinforcement Learning for Malware Detection under Concept Drift applies reinforcement learning to drifting malware and adds a reject action. It assumes ground-truth labels are available and does not consider what verification costs. We take the opposite stance: verification is the scarce resource.
Baselines
The naive reference point is uniform allocation at the same total budget. Every prompt gets the same number of attempts, as in standard RLOO. A second, stronger naive point is uniform over-sampling at several times that budget, in the style of DAPO. This version is drift-robust by construction, and it tells us what robustness costs. AR3PO reports that DAPO-style sampling uses 4.2× more rollouts than AR3PO on Qwen2.5-7B. AR3PO itself reaches an average of 43.1 across Math500, Minerva Math and OlympiadBench, against 42.9 for DAPO and 42.2 for GRPO. Our goal is to match uniform over-sampling's accuracy under drift while staying near VIP's cost.
The strongest predictive competitor is VIP. It is the method whose stationarity assumption we attack, and on stationary data it is the one to beat. The file reports VIP's gain over RLOO on Qwen2.5-Math-1.5B on AIME 2024: +12.3 Pass@32 and +6.3 Mean@32. It also reports Bamboogle exact match rising from 10.4% to 17.6%. We found no absolute AIME number for VIP on Lacuna, only these deltas, so we will rerun VIP ourselves. We will use its released configuration on DAPO-MATH-17k with the same model, seeds, and an identical hyperparameter search of equal size for every method.
The strongest probe-based competitor is AR3PO. It samples a small first batch for every prompt and so cannot be fooled by a stale predictor, but it pays for this robustness by probing every prompt. On Qwen2.5-32B it matches DAPO's 34.0% on AIME 2024 at a ninefold lower rollout cost. We will run it at the same model scale and total budget as the other methods.
Beating these baselines means two things. Under covariate and adversarial drift, we must achieve higher Mean@32 than VIP at equal budget. Under drift, we must also match AR3PO's accuracy with measurably fewer total checker calls. Under stationary conditions, we must lose no more than one standard error to VIP. If a method wins under drift but loses clearly in the stationary condition, it does not count as a win.
Two ablations isolate the key ingredient. The first replaces the residual-based drift monitor with embedding novelty, which is just the Gaussian process variance. This tests whether prediction residuals matter. We expect novelty to catch topic shifts but miss the adversarial proposer. The second keeps the monitor but drops the information term and only resets the flagged neighborhoods' posteriors to the prior. This tests whether the objective change itself matters.
Why not just…?
Why not just make the Gaussian process forget faster? Raising the process noise or using a sliding window is the most plausible simpler fix, and we treat it as a real threat. Uniform forgetting pulls every posterior mean back toward the prior, including on prompts that have not moved, so it drifts toward uniform allocation and gives up VIP's savings. The equation above also shows that the larger posterior variance does not, by itself, attract attempts. We will sweep forgetting rates and plot each one's cost–accuracy curve against ours. If some forgetting rate matches our method in both stationary and drifted conditions, then the targeted monitor is unnecessary and we will report that.
Why not just use AR3PO, which observes every prompt directly? AR3PO is drift-robust in its estimate of each prompt's pass rate, but it pays an initial probe for every prompt and loses the predictive savings. Its replay of past correct responses also assumes the checker never changes. Under our checker-tightening condition, we expect reused responses that are now wrong to inject wrongly signed advantages. The experiment measures this directly, as the fraction of reused responses that fail re-verification and the accuracy cost of using them.
Why not just reserve a random fraction of the budget for exploration? Random scouting finds a drifted region at a rate proportional to the region's share of the prompt pool. An adversary concentrates on a small, surface-similar region, so random scouting should be slow exactly when it matters. We will include epsilon-scouting at matched budget. If it matches us under the adversarial proposer, the residual monitor adds nothing, and we will say so.
Why not just use standard drift-aware active learning on the security side? LAMDA reports that a leading active-learning drift adaptation method with a 400-label budget reaches about 92% F1 on APIGraph but only 43% on LAMDA. That gap motivates rather than refutes our approach. Our allocator in the security transfer check is closely related to active learning, though, so we compare against uncertainty sampling and DREAM-style detection at identical budgets rather than claim a new category.
Proposed Experiments
The primary testbed is RLOO on Qwen2.5-Math-1.5B trained on DAPO-MATH-17k, evaluated on AIME 2024, Math500, Minerva Math and OlympiadBench, under three conditions.
The first condition is stationary training, which checks that we do not regress against VIP.
The second is staged covariate shift. Prompts arrive in topic blocks, and new blocks are introduced partway through training, mimicking the longitudinal splits of LAMDA. That benchmark reports LightGBM F1 falling from 97.49% on in-distribution data to 59.48% in the near future and 47.24% in the far future. Its false-negative rate rises from 1.47% to 64.10%.
The third is an adversarial proposer. It is a second model rewarded for generating perturbed variants of mastered problems that the allocator assigns the minimum budget but that the solver fails. A matched-budget proposer without the allocator-targeting term serves as control.
For checker drift, we add a code condition on MBPP and APPS, following the execution-reward setup of Execution-based Code Generation using Deep Reinforcement Learning. Midway through training, the test harness is tightened with edge-case tests, so previously correct solutions fail.
Metrics are AIME Pass@32 and Mean@32, the math-suite average, MBPP pass rate, total checker calls, starvation rate, and recovery time.
The security transfer check runs on the LAMDA monthly stream. The "rollout" there is a call to an expensive labeler, simulated by revealing the label at a per-month budget. The policy is a three-action detector with labels Goodware, Malware and Reject, as in DRMD. We report per-period F1, false-negative rate and area-under-time against uncertainty sampling, DREAM-style drift detection, and test-time adaptation as in MADCAT: Combating Malware Detection Under Concept Drift with Test-Time Adaptation. MADCAT reports mean F1 of 0.928 against 0.753 for a static MLP on APIGraph. It cannot choose where to spend verification, so it isolates the value of that choice.
The decisive check is the adversarial-proposer condition. If our method's starvation rate and Mean@32 are no better than those of fast-forgetting VIP or epsilon-scouting at matched budget, the central claim fails. If our method beats them there, stays within noise of VIP when the data is stationary, and uses fewer checker calls than AR3PO under drift, then targeted, residual-triggered probing is the right way to spend a verification budget on a stream that moves.
References
- Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
- Better LLM Reasoning via Dual-Play
- Combating Concept Drift with Explanatory Detection and Adaptation for Android Malware Classification
- Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse
- LAMDA: A Longitudinal Android Malware Benchmark for Concept Drift Analysis
- DRMD: Deep Reinforcement Learning for Malware Detection Under Concept Drift
- Execution-based Code Generation using Deep Reinforcement Learning
- MADCAT: Combating Malware Detection Under Concept Drift with Test-Time Adaptation