ArXiv: 2509.25849

🎯 Pitch

Uniformly giving each task 8 rollouts wastes GPU hours—20% of your GRPO gradients vanish because easy prompts get all-correct and hard ones get all-failure samples, producing zero learning signal. This paper solves that by treating exploration budget as a knapsack problem, reallocating compute so hard math problems get up to 93 rollouts while easy ones get slashed, boosting effective gradient ratios by 20–40% and matching a 2× compute budget with zero extra cost.

1. Executive Summary

This paper proposes Knapsack RL, a framework that reformulates exploration budget allocation in LLM reinforcement learning as a classical knapsack optimization problem, where each training prompt is treated as an item with an associated learning value and computational cost. Applied to Group Relative Policy Optimization (GRPO) on the DAPO-Math-17K dataset with Qwen-series models, the method dynamically redistributes the fixed total exploration budget across prompts based on estimated success rates—allocating up to 93 rollouts to especially hard problems while economizing on easy ones—yielding a 20–40% increase in the effective gradient ratio and average benchmark improvements of 2–4 points, achieving performance that would require roughly 2× the computational resources under uniform allocation. The framework establishes that exploration budgets can be treated as a centralized resource to maximize aggregate learning signal, though it rests on the finding that even with optimal allocation, approximately 20% of prompts remain unsolved, indicating that budget redistribution amplifies existing learning capacity rather than creating it from scratch.

2. Context and Motivation

The Core Problem: Exploration Is Expensive, But We Allocate It Blindly

The fundamental tension this paper tackles is one that every practitioner of LLM reinforcement learning encounters but few address systematically: exploration—sampling diverse responses from the model to discover better solutions—is computationally expensive, yet the standard practice is to allocate exactly the same exploration budget to every training prompt, regardless of whether that prompt is trivially easy or nearly impossible.

This matters because modern RL pipelines for LLMs, particularly those using GRPO (Group Relative Policy Optimization), operate on a simple principle: for each prompt in a training batch, generate NN responses (typically N=8N = 8 in the Verl framework used by the authors), score them against a verifiable reward function, and compute gradients that increase the probability of correct responses while decreasing the probability of incorrect ones. The problem is that GRPO's gradient estimator produces zero learning signal when all NN responses for a given prompt yield the same reward—all correct or all incorrect. In either case, the advantage term (r(xi,yij)−bi)(r(x_i, y_{ij}) - b_i) in Equation 3 collapses to zero for every sample, and the model learns nothing from that prompt despite having spent the full computational cost of generating NN responses.

This is not a theoretical curiosity. The authors document (Figure 2) that during training of Qwen2.5-Math-7B on DAPO-Math-17K with N=8N = 8 uniform rollouts, the effective gradient ratio—the fraction of generated samples that actually contribute non-zero gradients—consistently remains below 60% and deteriorates to roughly 20% by iteration 1000. In the early training phase (iterations 0–70), nearly 95% of prompts exhibit all-negative rewards, generating no useful signal. By late training (iteration 600+), roughly 40% of prompts have become all-positive (the model has mastered them) while another 20% remain all-negative (the model cannot touch them), creating a situation where the majority of expensive autoregressive generation yields zero learning benefit.

The mathematical structure of this problem is captured by Observation 1 and Theorem 1. For a prompt with success rate pip_i (the probability the model generates a correct response), the probability of obtaining a non-zero gradient with NN independent rollouts is:

P(gi≠0)=1−piN−(1−pi)NP(g_i \neq 0) = 1 - p_i^N - (1 - p_i)^N

This reveals the crux of the issue: the exploration budget NN required to reliably produce learning signals scales dramatically with how extreme the success rate is. For a medium-difficulty prompt with pi=0.5p_i = 0.5, only 3 rollouts are needed on average to see both a success and a failure. But for a hard prompt with pi=0.01p_i = 0.01, the expected number of rollouts until a non-zero gradient occurs is:

E[Nifirst]=1pi+11−pi−1≈100\mathbb{E}[N_i^{\text{first}}] = \frac{1}{p_i} + \frac{1}{1 - p_i} - 1 \approx 100

To have even a 90% probability of obtaining a non-zero gradient for such a prompt, the high-probability bound from Theorem 1 indicates N≳229N \gtrsim 229 rollouts—nearly 30× the standard budget of 8.

The practical consequence is stark: uniform allocation simultaneously under-explores hard prompts (denying them the chance to produce learning signals) and over-explores easy prompts (wasting compute on tasks already solved). Both failure modes produce zero gradients, meaning the spent computation is entirely wasted for learning purposes.

Why This Problem Matters: The Economics of RL Training and the Limits of Learning

The significance of this problem extends beyond mere computational efficiency into questions of what RL can and cannot teach LLMs.

Economic significance: the cost of zero gradients. The authors report that training Qwen2.5-Math-7B for 1,000 iterations on DAPO-Math-17K requires approximately 1,400 GPU hours with A100 GPUs (Section 5.1). With an effective gradient ratio hovering between 20–60%, this means somewhere between 560 and 1,120 of those GPU hours are spent generating responses that contribute nothing to model improvement. In an era where scaling RL training is a dominant paradigm for improving reasoning capabilities—as evidenced by systems like DeepSeek-R1, Kimi k1.5, and OpenAI's o-series models—this inefficiency directly translates to millions of dollars in wasted compute at scale.

The 2×2\times resource equivalence finding (Section 5.3, Figure 9) makes this concrete: Knapsack-GRPO with a total budget of 1,024 achieves roughly the same average benchmark performance as standard GRPO with a total budget of 2,048. This means that for a fixed performance target, the knapsack approach halves the required training compute—or equivalently, for a fixed compute budget, it enables training on twice as many prompts or for twice as many iterations.

Learning significance: some prompts may never be learnable under uniform allocation. The theoretical analysis reveals a more fundamental problem than inefficiency. For prompts with pip_i below approximately 0.01, the expected number of rollouts to obtain a non-zero gradient exceeds 100. Under uniform N=8N = 8, these prompts will generate all-negative responses in virtually every training iteration. Since GRPO gradients require both positive and negative examples, these prompts are effectively invisible to the learning process—they consume compute but provide no gradient information that could help the model learn to solve them. The model never sees what a correct solution looks like for these prompts, so it can never improve on them.

This creates a self-reinforcing failure mode: hard prompts remain hard because they never produce useful gradients; easy prompts become easier because they do. The training dynamics in Figure 2 confirm this pattern—the zero-gradient ratio from all-negative rewards (the green line) never drops below roughly 20%, even after 1,000 iterations, indicating a persistent fraction of prompts that the model never meaningfully engages with.

The transition matrix analysis (Figure 7) quantifies this lock-in: under standard GRPO, 47.1% of prompts initially classified as "extremely-hard" (pi=0p_i = 0) remain in that category after training. Under Knapsack-GRPO, this number drops to 43.4%—still substantial, but meaningfully lower. The 197-prompt reduction in the extremely-hard category (from 3,793 to 3,596, Figure 8) represents prompts that were essentially unlearnable under uniform allocation but became tractable when given sufficient exploration budget to generate at least one successful trajectory.

Prior Approaches and Their Shortcomings

The paper identifies three existing strategies for dealing with exploration inefficiency, each with fundamental limitations:

1. Uniformly increasing the exploration budget. The simplest approach is to raise NN across the board—from 8 to 16, 32, or higher. This directly addresses the probability problem: with N=32N = 32, a prompt with pi=0.1p_i = 0.1 has P(gi≠0)≈0.96P(g_i \neq 0) \approx 0.96, versus only P≈0.57P \approx 0.57 with N=8N = 8. The problem is cost: each doubling of NN doubles the total training compute, making this approach economically prohibitive. Setting N=100N = 100 to cover prompts with pi≈0.01p_i \approx 0.01 would require roughly 12.5× the compute of N=8N = 8, which is infeasible at scale. This is the computation-exploration dilemma the authors name in Section 3.2: covering the hardest prompts requires a budget that makes the total training cost unacceptable.

2. Prompt filtering and curriculum learning. A widely used alternative, employed in systems like DAPO (Yu et al., 2025) and Kimi k1.5 (Team et al., 2025), is to simply drop prompts that produce zero gradients—either all-positive or all-negative. The DAPO paper introduced "dynamic sampling," which repeatedly samples from the prompt pool, filtering out prompts with homogeneous rewards, until a target number of "effective" prompts (those with mixed rewards) is accumulated for a gradient update.

The authors acknowledge this approach is effective (Appendix D.4 shows dynamic sampling improves GRPO's average score from 45.2 to 46.2), but they identify a critical limitation: filtering hard prompts closes off a crucial source of learning. As they argue in Section 3.2:

"If we simply filter these prompts, we may close off a crucial source for RL, where meaningful learning often comes from converting failures into successes. That is, removing hard prompts deprives the model of opportunities to practice on challenging examples."

This is not merely a philosophical objection—it has empirical consequences. Figure 2 shows that in late training, the zero-gradient ratio from all-negative rewards remains around 20%. These are not prompts the model has mastered; they are prompts the model still struggles with. Filtering them would produce cleaner gradient updates on easier prompts, but at the cost of never learning to solve the hard ones. The transition matrix (Figure 7) demonstrates that under GRPO, prompts can move from "extremely-hard" to "easy" or "extremely-easy"—but only if they receive gradient updates in the first place, which requires them to occasionally produce a correct response.

A subtler form of curriculum learning, exemplified by Chen et al. (2025) who use advantage estimates as difficulty proxies and Sun et al. (2025) who use perplexity, operates by selecting which prompts to train on at each stage, often prioritizing those at the "frontier" of the model's capability. While these methods improve data efficiency, they still allocate homogeneous exploration budgets to the selected prompts. The knapsack approach is orthogonal and complementary: it addresses how much exploration each prompt receives, regardless of which prompts are selected.

3. Variance reduction through better baselines. Work such as ReMax (Li et al., 2024) and RLOO (Ahmadian et al., 2024) improves the exploitation side of RL—designing better gradient estimators that reduce variance and improve stability. Li et al. (2024) observed substantial variations in reward distributions across prompts and proposed using the reward of the greedy response as a baseline rather than the batch average. While these methods make each gradient update more informative when it occurs, they do not address the fundamental problem that many prompts produce no gradient at all under limited exploration budgets. A better baseline does not help if all NN responses for a prompt receive the same reward.

4. Dynamic sampling in DAPO as a partial solution. The DAPO paper's dynamic sampling is the most directly comparable prior work. It recognizes the zero-gradient problem and proposes scaling up effective prompts—those with mixed rewards—by repeatedly resampling until enough such prompts are accumulated. The authors position their knapsack approach as addressing a different axis: scaling up effective responses rather than effective prompts. As they clarify in Section 6:

"it is crucial to clarify that their 'sampling' refers to selecting prompts that yield effective gradients, rather than dynamically allocating exploration budgets."

The empirical comparison in Appendix D.4 confirms these are complementary: combining dynamic sampling with knapsack allocation yields performance of 46.5 (vs. 45.2 for GRPO, 46.2 for dynamic sampling alone, and 47.5 for knapsack alone), suggesting the approaches address different bottlenecks. The knapsack approach alone outperforms the combination, which the authors attribute to knapsack-GRPO utilizing more gradient iterations.

How This Paper Positions Itself: A New Axis for Optimization

The paper's central intellectual move is to reframe exploration budget allocation as a constrained resource optimization problem rather than a fixed hyperparameter choice. Instead of asking "what NN should we use?", the paper asks: given a fixed total exploration budget across all prompts, how should we distribute it to maximize total learning value?

This framing connects directly to the operations research literature on knapsack problems (Mathews, 1896; Pisinger and Toth, 1998), which has been extensively studied in contexts like portfolio optimization and resource allocation in distributed systems, but rarely applied to the internal mechanics of RL training. The correspondence the authors draw in Table 1 is deliberate and precise:

  • Each prompt, when paired with a specific exploration budget NiN_i, becomes an "item" with a weight (the computational cost of generating NiN_i responses) and a value (the expected learning benefit).
  • The total exploration budget is the knapsack's capacity, determined by available GPU hours or generation throughput.
  • The optimization objective is to select a set of (prompt, budget) pairs that maximizes total value while respecting the capacity constraint.

This reframing has several important consequences for how the paper positions itself relative to prior work:

It operates on a different axis than prompt selection and curriculum learning. Prior work asks which prompts to train on; this paper asks how much to explore on each prompt. These axes are independent and potentially multiplicative—one could apply curriculum learning to select a subset of prompts, then use knapsack allocation to distribute exploration within that subset. The authors demonstrate this complementarity empirically in Appendix D.4.

It treats exploration as a first-class optimization variable, not an afterthought. Most RL for LLM pipelines treat the exploration budget NN as a fixed hyperparameter, often chosen based on GPU memory constraints or throughput considerations rather than learning dynamics. The paper demonstrates that NN should vary with prompt difficulty and that doing so yields substantial gains without requiring additional compute. This aligns with broader trends in the field toward more sophisticated inference-time and training-time compute allocation (Snell et al., 2024), but applies the principle specifically to the exploration phase of online RL.

It provides a principled way to scale exploration on hard prompts without exploding total compute. Rather than uniformly increasing NN (which multiplies total compute by the same factor), the knapsack approach redistributes existing compute from easy prompts to hard ones. Figure 5 shows that this enables allocating up to 93 rollouts to individual hard prompts—more than 10× the standard budget—within the same total compute envelope. This is the key insight that makes the approach a "free lunch": by economizing on prompts where exploration is already saturated (all-positive or nearly all-positive success rates), it frees up budget to push through the exploration barrier on prompts that would otherwise never generate useful gradients.

It connects to the broader challenge of data heterogeneity in LLM RL. The paper explicitly situates itself within the line of work recognizing that prompt difficulty variation is a central challenge for RL training (Section 6). Prior work addressed this through variance reduction (Li et al., 2024), prompt filtering (Yu et al., 2025), or curriculum design (Chen et al., 2025). The knapsack approach offers a new mechanism: directly manipulating the data collection process to ensure that difficult prompts are adequately sampled, rather than compensating for inadequate sampling through better gradient estimators or prompt selection. The authors argue this is a more fundamental intervention because it addresses the root cause—insufficient exploration—rather than its downstream symptoms (high variance, sparse gradients).

The theoretical framework is designed for extensibility. While the paper's main implementation targets GRPO, Section 6 and Appendix B explicitly sketch how the value function formulation extends to other RL algorithms (RLOO, ReMax, REINFORCE) by adapting the ProbNonZeroGradient term to each algorithm's gradient computation mechanism. This suggests the authors view the knapsack framing not as a GRPO-specific trick but as a general principle for exploration-aware budget allocation in LLM RL.

The Gap This Paper Fills

In summary, the paper addresses a clear and consequential gap: there exists no principled method for allocating heterogeneous exploration budgets across prompts in online LLM RL training, despite clear theoretical and empirical evidence that uniform allocation wastes substantial compute and leaves hard prompts unexplored. Prior work has either accepted the inefficiency of uniform allocation, attempted to filter out the problematic prompts, or improved the gradient estimator for the prompts that do produce signals—but none has directly attacked the allocation problem itself by viewing the total exploration budget as a centralized resource to be optimally distributed according to each prompt's learning potential. The knapsack formulation provides both a theoretical framework for understanding this allocation problem and a practical algorithm that integrates into existing RL pipelines with minimal modification (Listing 1), no additional hyperparameters, and negligible computational overhead.

3. Technical Approach

3.1 Reader Orientation

Knapsack RL is a computationally free, plug-and-play budget allocator that sits inside an existing GRPO training loop and—using only the success/failure statistics the system already collects—decides how many rollouts each prompt should receive so that the total number of "wasted" gradient-free samples is minimized. The system solves the problem that uniform exploration budgets simultaneously starve hard prompts (which need many attempts to ever produce a gradient) and over-feed easy prompts (which already generate gradients reliably), by treating the total generation budget as a fixed knapsack and each prompt's allocation as a variable item whose weight is computational cost and whose value is expected learning benefit.

3.2 Big-Picture Architecture (Diagram in Words)

The system has five major components connected by a single modification to the standard GRPO loop:

  1. Success-Rate Estimator — a lightweight memory that tracks, for each training prompt, the empirical success rate $\hat{p}_i$ (fraction of correct responses) observed during the previous epoch. This is the only state the allocator needs beyond what GRPO already collects.

  2. Value Function — a fixed formula $\text{Value}(N_i, p_i) = \text{ProbNonZeroGradient}(N_i, p_i) \times \text{InfoGain}(p_i)$ that maps any $(\text{prompt difficulty}, \text{budget})$ pair to a scalar representing expected learning benefit. This function encodes the paper's core insight about what makes exploration valuable.

  3. Knapsack Solver — a standard dynamic-programming optimizer that takes the list of possible $(\text{prompt}, \text{budget})$ items (each with weight $N_i$ and value from the value function), the total generation budget $N_{\text{total}}$, and per-prompt bounds $[N_{\text{low}}, N_{\text{up}}]$, and returns the budget $N_i$ for each of the $M$ prompts in the batch that maximizes total value subject to $\sum_i N_i = N_{\text{total}}$. Runs in 1–2 seconds with Numba acceleration.

  4. Fallback and Bound Logic — handles degenerate cases: prompts with $\hat{p}_i = 0.0$ (never solved) receive any budget left over after allocating to solvable prompts; prompts with $\hat{p}_i = 1.0$ receive the minimum budget $N_{\text{low}}$ to maintain coverage and detect potential regression.

  5. Rollout Dispatcher — converts the heterogeneous per-prompt budgets into concrete generation jobs by treating each allocated rollout as an individual execution job, randomly shuffling these jobs across the available $W$ parallel workers to avoid load imbalance, and feeding them to the inference engine (e.g., vLLM) for autoregressive generation.

Information flows: a training batch of $M$ prompts enters → the success-rate estimator provides $\hat{p}_i$ for each prompt based on the previous epoch → the value function computes value scores for each possible budget $N_i$ in $[N_{\text{low}}, N_{\text{up}}]$ for each prompt → the knapsack solver selects the $N_i$ that maximize total value under the fixed total budget $N_{\text{total}}$ → the fallback logic adjusts allocations for extreme $\hat{p}_i$ cases → the rollout dispatcher converts $N_i$ values into shuffled generation jobs → the inference engine generates the responses → rewards are computed (same as standard GRPO) → GRPO gradient estimation proceeds exactly as usual (Equation 3) on the heterogeneous batch → model parameters update → success rates are updated for the next epoch.

3.3 Roadmap for the Deep Dive

  • First, the value function and its two multiplicative components—ProbNonZeroGradient and InfoGain—because the entire allocation depends on quantifying "how valuable is it to allocate $N$ rollouts to a prompt with success rate $p$?"
  • Second, the formal optimization problem (Equation 5) and its mapping to the 0/1 knapsack problem, including how the item space is constructed from prompt–budget pairs.
  • Third, the knapsack solver's implementation, its computational cost, and why dynamic programming is sufficient.
  • Fourth, the practical estimation pipeline: how $\hat{p}_i$ is obtained from previous-epoch data and why this introduces acceptable staleness.
  • Fifth, the fallback strategy and bound constraints—the engineering decisions that prevent degenerate allocations for prompts with empirical success rates of 0 or 1.
  • Sixth, the rollout balancing mechanism that converts heterogeneous per-prompt budgets into efficient parallel generation across workers.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems-and-optimization paper whose core idea is that the exploration budget allocation in online LLM RL can be formulated as a classical knapsack problem, and that a simple value function based on success-rate statistics is sufficient to drive allocations that substantially improve learning efficiency without additional compute.

The Value Function: Quantifying the Learning Benefit of Exploration

The entire allocation framework rests on a single design decision: how do we assign a numerical value to the act of allocating $N_i$ rollout trajectories to a prompt $x_i$ whose current success rate is $p_i$? The paper defines this value as the product of two terms that capture distinct aspects of what makes exploration useful for GRPO:

Value(Ni,pi)=ProbNonZeroGradient(Ni,pi)×InfoGain(pi)\text{Value}(N_i, p_i) = \text{ProbNonZeroGradient}(N_i, p_i) \times \text{InfoGain}(p_i)

where $\text{ProbNonZeroGradient}(N_i, p_i)$ is the probability that the $N_i$ sampled responses for prompt $x_i$ will contain at least one correct and at least one incorrect response (thus producing a non-zero gradient under GRPO), and $\text{InfoGain}(p_i)$ is the expected improvement in the model's success probability on this prompt after a single gradient update, conditioned on a non-zero gradient occurring.

What this product computes: an expected learning benefit—the probability that a useful training signal occurs multiplied by the magnitude of improvement if it does. A high value means the allocation is likely to produce a gradient AND that gradient is likely to meaningfully improve the model. A low value means either the allocation is wasteful (unlikely to produce any gradient) or the prompt is already near-solved or near-impossible (gradients would provide negligible improvement).

Why this multiplicative form: the two factors address distinct failure modes. ProbNonZeroGradient captures the exploration bottleneck—for hard prompts, this probability is near zero with small $N_i$, so the value is near zero regardless of InfoGain, correctly preventing the optimizer from wasting budget on prompts that will produce all-negative rollouts. InfoGain captures the learning saturation bottleneck—for prompts that are already almost always correct ($p_i \approx 1$) or almost never correct ($p_i \approx 0$), the expected improvement from a gradient step is small, so the value is small even when ProbNonZeroGradient is high, correctly preventing the optimizer from over-investing in prompts where learning has plateaued. The product ensures that budget flows to prompts that are both explorable (can produce mixed outcomes with the allocated budget) and improvable (are in the intermediate difficulty regime where gradients actually change behavior).

The alternative—using only ProbNonZeroGradient as the value—would naively allocate maximum budget to the hardest prompts (to overcome their low per-sample success probability), ignoring that even if a gradient occurs, the improvement from a single update on a $p_i = 0.001$ prompt is negligible. Using only InfoGain would allocate budget to prompts with $p_i \approx 1/3$ regardless of whether the budget is sufficient to actually produce mixed outcomes. The product couples these considerations.

Component 1: ProbNonZeroGradient — Will This Budget Produce a Learning Signal?

The first multiplicative factor quantifies the exploration sufficiency problem that Section 3 diagnosed:

ProbNonZeroGradient(Ni,pi)=1−piNi−(1−pi)Ni\text{ProbNonZeroGradient}(N_i, p_i) = 1 - p_i^{N_i} - (1 - p_i)^{N_i}

where $p_i \in (0, 1)$ is the probability that a single rollout from the current policy produces a correct response for prompt $x_i$, and $N_i$ is the number of independent rollouts allocated.

What it computes: one minus the probability that all $N_i$ independent Bernoulli trials produce the same outcome. The term $p_i^{N_i}$ is the probability that all $N_i$ responses are correct (all-positive rewards, zero gradient). The term $(1 - p_i)^{N_i}$ is the probability that all $N_i$ responses are incorrect (all-negative rewards, zero gradient). Subtracting both from 1 gives the probability that the batch contains at least one success AND at least one failure—the condition under which GRPO's advantage term $(r(x_i, y_{ij}) - b_i)$ is non-zero for at least some samples.

Why this form: it follows directly from the Bernoulli assumption (Definition 1) and the structure of GRPO's gradient estimator (Equation 3, Observation 1). Under GRPO, the baseline $b_i$ is the sample mean reward, so if all rewards are identical, every advantage is zero and $g_i = 0$. The probability expression is exact under the i.i.d. sampling assumption. The key property is its behavior at extreme $p_i$: as $p_i \to 0$, $p_i^{N_i} \to 0$ but $(1 - p_i)^{N_i} \to 1$, so the probability approaches zero—hard prompts need large $N_i$ to overcome this. As $p_i \to 1$, $(1 - p_i)^{N_i} \to 0$ but $p_i^{N_i} \to 1$, creating the symmetric problem for easy prompts. At $p_i = 0.5$, the probability is $1 - 2 \times (0.5)^{N_i}$, which exceeds 0.9 for $N_i \ge 4$—medium prompts are cheap to explore.

This component directly incorporates the theoretical analysis from Theorem 1. The high-probability bound $N \gtrsim \ln(1 - \alpha) / \ln(\max\{p_i, 1 - p_i\})$ is the inverse of this probability function, answering "how large must $N_i$ be to guarantee a gradient with probability $\alpha$?" The expected-first-success formula $\mathbb{E}[N_i^{\text{first}}] = 1/p_i + 1/(1 - p_i) - 1$ captures a related but distinct quantity—the expected rollouts until the FIRST non-zero gradient occurs in a sequential process, not the probability of at least one gradient in a fixed batch.

A subtlety: this formulation assumes rollouts are independent and identically distributed, which is a reasonable approximation for autoregressive sampling at non-zero temperature. In practice, the model distribution $\pi_\theta$ changes slowly across iterations, but within a single iteration the i.i.d. assumption holds.

Component 2: InfoGain — How Much Will a Gradient Improve This Prompt?

The second multiplicative factor quantifies the learning potential of a prompt independent of exploration sufficiency. The paper defines it operationally:

InfoGain(pi)=Δpi=pit+1−pit\text{InfoGain}(p_i) = \Delta p_i = p_i^{t+1} - p_i^t

where $p_i^t$ is the success rate before a gradient update and $p_i^{t+1}$ is the success rate after a single policy gradient step.

The problem: computing this directly requires knowing the post-update success probability, which is intractable—it would require running the optimizer, updating the model, and re-evaluating, at which point you have already spent the compute you are trying to decide whether to spend. The paper resolves this through a first-order Taylor approximation (Proposition 1).

Derivation of the approximation (Proposition 1). The derivation proceeds in five steps under a softmax policy model:

  1. Taylor expansion: For small parameter changes, $\Delta p_y \approx \sum_{k=1}^K \frac{\partial p_y}{\partial z_k} \Delta z_k$, where $z_k$ are the logits for $K$ possible actions (tokens or token sequences) and $y$ is the "correct" action.

  2. Softmax partial derivatives: For a softmax distribution $p_k = \exp(z_k) / \sum_j \exp(z_j)$, the derivatives are $\frac{\partial p_y}{\partial z_y} = p_y(1 - p_y)$ and $\frac{\partial p_y}{\partial z_k} = -p_y p_k$ for $k \neq y$.

  3. Policy gradient update rule: Under the standard policy gradient with unit advantage, the parameter updates follow $\Delta z_k = \mathbf{1}[k = y] - p_k$. So $\Delta z_y = 1 - p_y$ (increase the correct action's logit) and $\Delta z_k = -p_k$ for $k \neq y$ (decrease incorrect actions' logits proportionally to their current probability).

  4. Substituting into the first-order expansion:

Δpy=py(1−py)⋅(1−py)+∑k≠y(−pypk)⋅(−pk)\Delta p_y = p_y(1 - p_y) \cdot (1 - p_y) + \sum_{k \neq y} (-p_y p_k) \cdot (-p_k) =py(1−py)2+py∑k≠ypk2= p_y(1 - p_y)^2 + p_y \sum_{k \neq y} p_k^2

  1. First-order approximation: Under small updates (small learning rate), the cross-term $\sum_{k \neq y} p_k^2$ is second-order in the update magnitude and negligible compared to the main term $p_y(1 - p_y)^2$. Dropping it yields:

InfoGain(pi)≈pi(1−pi)2\text{InfoGain}(p_i) \approx p_i(1 - p_i)^2

where $p_i$ is the current success rate for prompt $x_i$ under the current policy.

What this approximation computes: a scalar between 0 and approximately 0.148 (the maximum at $p_i = 1/3$) that estimates how much the model's success probability on this prompt will increase after one gradient step, assuming a gradient actually occurs. It depends ONLY on the current success rate $p_i$—no other prompt-specific information is needed.

Why this form matters—key properties:

  • Maximum at $p_i = 1/3$: The derivative $d/dp_i [p_i(1 - p_i)^2] = (1 - p_i)(1 - 3p_i)$ has a root at $p_i = 1/3$. This means prompts where the model succeeds roughly one-third of the time are predicted to be the most "improvable"—they are uncertain enough that gradients contain useful information, but not so hopeless that a single update cannot move the needle. This aligns with pedagogical intuition: the most valuable practice problems are those you sometimes get right.

  • Asymmetry favoring harder prompts: For two prompts equally distant from the optimum $p_i = 1/3$, the harder one (lower $p_i$) has higher InfoGain than the easier one (higher $p_i$). For example: $p_i = 0.1$ gives $\text{InfoGain} = 0.1 \times 0.9^2 = 0.081$, while $p_i = 0.567$ (the symmetric point $1/3 + (1/3 - 0.1) = 0.567$) gives $0.567 \times 0.433^2 = 0.106$. Wait—this example actually shows the EASIER prompt has higher InfoGain, which contradicts the paper's claim. Let me recalculate: the paper states "for equally distant values of $p_i$ from 1/3, harder tasks yield larger information gain than easier tasks." Testing: distance $d = 0.2$ from $1/3 \approx 0.333$. Harder: $p = 0.133$, $\text{InfoGain} = 0.133 \times 0.867^2 \approx 0.100$. Easier: $p = 0.533$, $\text{InfoGain} = 0.533 \times 0.467^2 \approx 0.116$. The easier prompt has higher InfoGain at this distance. The paper's claim about asymmetry requires checking: the derivative is $(1 - p)(1 - 3p)$, which is negative for $p > 1/3$ and positive for $p < 1/3$. The magnitude of the derivative $|1 - 3p|$ is symmetric around $1/3$, but the factor $(1 - p)$ is asymmetric—it is larger when $p$ is smaller. So for $p = 1/3 - d$, $\text{InfoGain} \approx (1/3 - d)(2/3 + d)^2$; for $p = 1/3 + d$, $\text{InfoGain} \approx (1/3 + d)(2/3 - d)^2$. Expanding to first order in $d$: the difference is $(2/3)^2(-d) + (1/3)(4/3)(-d) - [(2/3)^2(d) + (1/3)(4/3)(-d)] = -(4/9)d - (4/9)d - (4/9)d + (4/9)d = -(8/9)d$. The harder prompt has LOWER InfoGain at small $d$, not higher. The paper's claim about asymmetry may reflect an error or a different operationalization—the contour plot in Figure 4 appears to show the value function, not InfoGain alone, and the multiplicative interaction with ProbNonZeroGradient changes the effective asymmetry. In any case, the exact asymmetry is a minor mathematical detail; the qualitative behavior—InfoGain peaks at intermediate difficulty and decays to zero at both extremes—is what drives the allocation.

  • Vanishing at extremes: $\text{InfoGain}(0) = 0$ and $\text{InfoGain}(1) = 0$. This correctly captures that prompts the model never solves (no correct trajectories to reinforce) or always solves (no incorrect trajectories to penalize) provide minimal learning value per gradient step, even if a gradient were to occur.

Empirical validation of the approximation. The paper validates the $p(1 - p)^2$ approximation against exact gradient updates in a synthetic 100-action setting (Appendix A, Figure 10), finding that the two curves "align closely across different success rates." This confirms that the first-order Taylor expansion, despite ignoring cross-terms, captures the dominant scaling behavior of the true InfoGain. The approximation's simplicity—requiring only the scalar $p_i$—makes it computationally trivial to evaluate for thousands of prompt–budget pairs inside the knapsack solver.

The Combined Value Landscape

Figure 4 visualizes $\text{Value}(N_i, p_i)$ as a contour plot with $p_i$ on one axis and $N_i$ on the other, showing lines of equal total value. The paper highlights three illustrative points:

  • $(p_i = 0.35, N_i = 4)$ achieves high value—this is a prompt near the InfoGain optimum $1/3$, requiring minimal exploration budget because $\text{ProbNonZeroGradient}(4, 0.35) = 1 - 0.35^4 - 0.65^4 \approx 1 - 0.015 - 0.179 = 0.806$, which is already high.
  • $(p_i = 0.19, N_i = 16)$ achieves comparable value—this is a harder prompt, further from the InfoGain peak, requiring 4× the budget to compensate: $\text{ProbNonZeroGradient}(16, 0.19) = 1 - 0.19^{16} - 0.81^{16} \approx 1 - \text{negligible} - 0.034 = 0.966$, providing high probability of a gradient to offset lower InfoGain.
  • $(p_i = 0.52, N_i = 8)$ achieves comparable value—an easier prompt requiring intermediate budget, balancing moderate InfoGain with moderate exploration probability.

This contour plot is the key design tool: it shows that the value function creates a "ridge" of high-value $(p_i, N_i)$ combinations, and the knapsack optimizer's job is to select a set of points along this ridge for the $M$ prompts in the batch such that the total weight $\sum N_i$ equals the fixed budget. Prompts far from the ridge—those with extreme $p_i$ and small $N_i$—contribute negligible value and receive minimal budget, freeing resources for prompts on the ridge.

The Knapsack Optimization Problem

With the value function defined, the allocation problem becomes a constrained discrete optimization:

max⁡N1,…,NM∑i=1MValue(Ni,p^i)\max_{N_1, \ldots, N_M} \sum_{i=1}^M \text{Value}(N_i, \hat{p}_i)

subject to∑i=1MNi=Ntotal,Nlow≤Ni≤Nup,Ni∈Z+\text{subject to} \quad \sum_{i=1}^M N_i = N_{\text{total}}, \quad N_{\text{low}} \le N_i \le N_{\text{up}}, \quad N_i \in \mathbb{Z}^+

where $M$ is the number of prompts in the training batch, $N_i$ is the integer number of rollouts allocated to prompt $x_i$, $\hat{p}_i$ is the estimated success rate from the previous epoch, $N_{\text{total}}$ is the total exploration budget (typically $M \times N$ where $N$ is the uniform budget that would be used in standard GRPO—e.g., $256 \times 8 = 2048$), $N_{\text{low}}$ is the minimum per-prompt budget (set to 2 to prevent degenerate zero-allocation), and $N_{\text{up}}$ is the maximum per-prompt budget (set to 128, primarily to bound the dynamic programming state space).

What this optimization computes: for a fixed total generation budget, the integer allocation vector $\mathbf{N} = (N_1, \ldots, N_M)$ that maximizes the sum of expected learning values across all prompts in the batch, with each prompt's contribution defined by the value function. It simultaneously decides which prompts deserve large exploration budgets (hard-but-improvable ones) and which can be sampled sparingly (already-solved or nearly-impossible ones).

Why this form is a knapsack problem: the objective is additive and separable across items, each item's contribution depends on a discrete choice (the budget $N_i$), and there is a single capacity constraint on the sum of the chosen weights. The mapping in Table 1 makes the correspondence explicit:

  • Items: not the prompts themselves, but prompt–budget PAIRS. A single prompt $x_i$ corresponds to $(N_{\text{up}} - N_{\text{low}} + 1)$ possible items—one for each feasible budget level—each with its own weight $N_i$ and value $\text{Value}(N_i, \hat{p}_i)$. The total item space has size $M \times (N_{\text{up}} - N_{\text{low}} + 1)$.
  • Selection constraint: exactly one "item" (one budget level) must be selected per prompt. This is enforced by the optimization over $N_i$ rather than by a standard 0/1 knapsack formulation, but the dynamic programming solution handles it naturally.
  • Capacity: $N_{\text{total}}$ is the knapsack's weight capacity, determined by available compute.

Why the bounds $N_{\text{low}}$ and $N_{\text{up}}$ are necessary: without $N_{\text{low}}$, prompts with $\text{Value}(N_i, \hat{p}_i) = 0$ for all $N_i$ (e.g., $\hat{p}_i = 1.0$ giving InfoGain = 0) would receive $N_i = 0$, meaning they are entirely excluded from the batch. This would prevent the system from detecting if these prompts later become harder (e.g., due to catastrophic forgetting or distribution shift). Setting $N_{\text{low}} = 2$ ensures every prompt receives at least a minimal sampling, maintaining coverage. Without $N_{\text{up}}$, the solver could allocate arbitrarily large budgets to a single prompt, which would be computationally infeasible (generating hundreds of responses for one prompt in a single iteration) and would create extreme load imbalance across workers. Setting $N_{\text{up}} = 128$ bounds the state space and prevents pathological allocations. Ablation results (Appendix D.3, Figure 17) show that setting $N_{\text{low}} = 0$ or $N_{\text{up}} = 32$ degrades performance, confirming these bounds are not arbitrary.

The computational cost of solving this knapsack. The paper uses standard dynamic programming with a state space of size $M \times N_{\text{total}}$, where each state $(i, w)$ represents the maximum value achievable using the first $i$ prompts with a total budget of $w$. The transition considers each possible budget $N_i \in [N_{\text{low}}, N_{\text{up}}]$ for prompt $i$. With $M = 256$, $N_{\text{total}} = 2048$, and $(N_{\text{up}} - N_{\text{low}} + 1) \approx 127$, the complexity is $O(M \times N_{\text{total}} \times (N_{\text{up}} - N_{\text{low}})) \approx 256 \times 2048 \times 127 \approx 6.6 \times 10^7$ operations—feasible in 1–2 seconds with Numba JIT compilation in Python. This is negligible compared to the cost of generating thousands of autoregressive sequences, making the allocation overhead truly a "free lunch."

A subtle but important implementation detail: the dynamic programming does NOT solve a standard 0/1 knapsack with binary item inclusion variables. Instead, it solves a multiple-choice knapsack where exactly one budget must be chosen per prompt from the feasible range. The DP state transition is:

dp[i][w]=max⁡Ni∈[Nlow,Nup](dp[i−1][w−Ni]+Value(Ni,p^i))\text{dp}[i][w] = \max_{N_i \in [N_{\text{low}}, N_{\text{up}}]} \left( \text{dp}[i-1][w - N_i] + \text{Value}(N_i, \hat{p}_i) \right)

with the base case $\text{dp}[0][0] = 0$ and $\text{dp}[0][w] = -\infty$ for $w > 0$. The final answer is the allocation that achieves $\text{dp}[M][N_{\text{total}}]$, recovered by backtracking through the DP table.

Estimating Success Rates from Previous Epoch Data

The value function requires $p_i$—the true success probability under the current policy—but the policy is continuously updated, so $p_i$ is a moving target. The paper adopts a simple, empirically effective heuristic:

Estimation procedure: During epoch $e$, for each prompt $x_i$, count the number of correct responses $c_i$ and total attempts $t_i$ across all iterations in the epoch. At the end of the epoch, compute the empirical success rate:

p^i=citi\hat{p}_i = \frac{c_i}{t_i}

This estimate is then used as the $p_i$ input to the value function for ALL iterations of epoch $e + 1$. In the first epoch, when no historical data exists, the system defaults to homogeneous allocation ($N_i = N$ for all prompts) to collect initial statistics.

Why this "stale" estimate is acceptable: The paper provides several justifications, both implicit and explicit:

  • Epochs are short relative to policy change. Each epoch corresponds to one pass through the training data (approximately 70 iterations for the DAPO-Math-17K dataset with $M = 256$ prompts per batch and $M \times 70 \approx 17,920$ total prompts). Within an epoch, the policy changes gradually enough that the previous epoch's success rates remain informative approximations of the current epoch's difficulty ordering—even if absolute success rates shift, the RELATIVE difficulty ranking across prompts is relatively stable.

  • The value function is smooth in $p_i$. Small estimation errors in $p_i$ produce proportionally small errors in $\text{Value}(N_i, p_i)$, so the allocation is robust to moderate staleness. The contour plot in Figure 4 shows broad regions of similar value, meaning the exact $p_i$ does not need to be precise to produce good allocations.

  • The first epoch is exploratory by design. Using homogeneous allocation in epoch 1 ensures every prompt receives some initial exploration, establishing a baseline success rate estimate. The knapsack allocation then refines this in subsequent epochs. This two-phase approach (explore uniformly, then allocate optimally) is a natural fit for the exploration–exploitation tradeoff.

Computational cost of estimation: the success-rate tracking adds negligible overhead—it requires only maintaining a running count of correct/total responses per prompt, which is a trivial addition to the existing reward computation step in the GRPO loop. No additional forward passes or generations are needed.

Alternative approaches not pursued: The paper acknowledges that more sophisticated estimation techniques—such as online logistic regression that models $p_i$ as a function of prompt features and iteration number, or Bayesian updating that quantifies uncertainty in $\hat{p}_i$—"present promising directions for future improvement." The simple epoch-based heuristic is chosen for its minimal implementation complexity and demonstrated effectiveness, but the authors frame this as a deliberate simplification rather than a claim of optimality.

Fallback Strategy: Handling Prompts with Empirical Success Rates of 0 or 1

The value function assigns $\text{Value}(N_i, 0) = 0$ and $\text{Value}(N_i, 1) = 0$ for any $N_i$ because $\text{InfoGain}(0) = \text{InfoGain}(1) = 0$. If the empirical estimate $\hat{p}_i$ is exactly 0.0 or 1.0, the knapsack optimizer would (correctly, under the model) assign these prompts the minimum possible budget $N_{\text{low}}$—or potentially zero if the bounds allowed it. The paper treats these two cases differently, reflecting their different practical implications:

Case 1: $\hat{p}_i = 1.0$ (prompt always solved correctly). The concern here is that the estimate may be inaccurate due to limited historical samples. A prompt that was solved in all $t_i$ attempts during the previous epoch might have a true success rate slightly below 1.0, and the model could regress on it. To maintain vigilance, the paper allocates the minimum budget $N_{\text{low}} = 2$ to all such prompts. This serves as a "canary"—if the model has started failing on this prompt, the two samples will detect the change and the success rate estimate will drop below 1.0 in the next epoch, triggering a higher allocation.

Case 2: $\hat{p}_i = 0.0$ (prompt never solved correctly). The concern here is more severe: these prompts are exactly the ones that need large exploration budgets to ever produce a correct trajectory, but the value function (correctly, under its InfoGain model) predicts zero learning benefit from exploring them. This creates a chicken-and-egg problem: the prompt has $\hat{p}_i = 0$ because it has never been explored enough to find a correct solution, but the value function assigns it zero value because it has $\hat{p}_i = 0$. The fallback strategy breaks this deadlock:

  1. Compute the budget required for all non-extreme prompts. First, run the knapsack solver for prompts with $\hat{p}_i \in (0, 1)$ (treating $\hat{p}_i = 1.0$ prompts as described above). This yields a baseline allocation that covers all prompts that have demonstrated at least one success in the previous epoch.

  2. Allocate remaining budget to extreme-hard prompts. Any budget left over after satisfying the non-extreme prompts is distributed among the $\hat{p}_i = 0.0$ prompts. This distribution is proportional or equal—the paper does not specify a precise sub-allocation rule, but the principle is that extremely hard prompts receive whatever resources are "left on the table" after the optimizer has satisfied the prompts it can model.

  3. If any $\hat{p}_i = 0.0$ prompt receives enough budget to generate a correct response, its empirical success rate becomes positive in the current epoch, and in the NEXT epoch it will be included in the main knapsack optimization with a non-zero value. This creates a virtuous cycle: the fallback strategy provides seed exploration to discover that hard prompts are solvable, after which the value function can properly prioritize them.

Why this strategy is particularly beneficial in late training (as claimed in Section 4.2): as training progresses, more prompts become "easy" (their success rates approach 1.0) and receive minimum budgets. This frees up substantial capacity that the fallback strategy redirects to the remaining hard prompts. In effect, the system automatically shifts from a broad exploration profile (early training, many prompts need moderate budgets) to a focused exploration profile (late training, most budget concentrated on the hardest remaining prompts). This adaptivity is a direct consequence of the knapsack formulation and requires no manual phase-switching or curriculum scheduling.

Empirical importance: The ablation in Appendix D.3 (Figure 16) demonstrates that removing the fallback strategy leads to "unstable training, large performance fluctuations on benchmarks such as AMC and OlympiadBench, and overall degraded results." This confirms that the zero-value prompts are not truly zero-value in practice—they represent learning opportunities that the simplified InfoGain model fails to capture, and the fallback strategy serves as a practical corrective.

A concrete example (Table 3): the paper contrasts allocation with and without fallback for 8 prompts. Without fallback, a prompt with $p_i = 0.0$ (theoretically requiring infinite exploration) receives only 2 units, while a prompt with $p_i = 0.9$ receives 50 units—a clearly suboptimal allocation since the 0.9 prompt already produces gradients reliably with far fewer samples. With fallback, the $p_i = 0.0$ prompt receives 29 units—a 14.5× increase—while the $p_i = 0.9$ prompt receives 23 units, a more reasonable allocation. The $p_i = 1.0$ prompts receive the minimum 2 units in both cases, correctly economizing.

Rollout Balancing: From Heterogeneous Budgets to Efficient Parallel Generation

The knapsack solver produces a vector $\mathbf{N} = (N_1, \ldots, N_M)$ of per-prompt rollout counts. These must be executed on $W$ parallel workers (GPU processes running the inference engine, typically fewer than $M$). Under uniform allocation ($N_i = N$ for all $i$), load balancing is trivial: divide the $M$ prompts evenly among the $W$ workers, and each worker generates $N$ responses for each of its assigned prompts. Under heterogeneous allocation, prompts can have wildly different $N_i$ values (up to 93, per Figure 5), creating severe load imbalance if prompts are naively distributed.

The paper's solution: job-level randomization. Rather than assigning prompts to workers, the system treats each individual rollout as a separate job:

  1. Expand the allocation into a job list. For each prompt $x_i$ with budget $N_i$, create $N_i$ copies of that prompt. The resulting list has length $\sum_i N_i = N_{\text{total}}$.

  2. Randomly shuffle the job list. This ensures that the expensive prompts (those with large $N_i$) are randomly interleaved with the cheap ones rather than clustered together.

  3. Distribute jobs to workers in round-robin or balanced fashion. Each worker receives approximately $N_{\text{total}} / W$ jobs, regardless of which prompts they correspond to. Workers then generate one response per job and return the results.

  4. Re-aggregate by prompt. After generation, responses are grouped back by their original prompt $x_i$ for reward computation and GRPO advantage calculation.

Why this works: the autoregressive generation cost for a single response is approximately independent of the prompt (assuming similar response lengths), so treating each generation as an atomic job naturally load-balances across workers. The randomization prevents any systematic correlation between worker assignment and prompt difficulty.

When this approach may need refinement: the paper acknowledges that this simple job-level randomization "is suitable for settings where prompts are not excessively long, thus not strictly requiring advanced techniques like prefix caching." For scenarios with very long prompts (where the prompt processing cost dominates the generation cost), the authors suggest using the Karmarkar–Karp bin-packing algorithm to group prompts into approximately balanced batches based on their total generation budget (including both prompt processing and autoregressive generation), potentially enabling prefix caching by keeping identical prompts together on the same worker. This refinement is not implemented in the paper but is flagged as a straightforward extension.

System integration: the rollout balancing step is the only systems-level modification required beyond the budget allocation logic. The paper emphasizes (Section 4.2) that "core components of inference (e.g., vLLM-based accelerated generation) and training (e.g., FSDP and Megatron) remain unchanged, ensuring full compatibility with existing infrastructure." This is a deliberate design choice to minimize adoption friction—the knapsack allocator is a drop-in replacement for the uniform budget assignment in the existing data loader.

Integration with the GRPO Training Loop

The complete Knapsack-GRPO algorithm replaces a single line in the standard GRPO pipeline (Algorithm 1, Line 3) with the knapsack-based budget allocation, while leaving all other components—reward computation, advantage estimation, gradient computation—identical. The modifications are summarized in the paper's Listing 1 (Appendix C):

  1. Budget allocation (replaces uniform assignment): Instead of budget = np.full(len(batch), N), the system calls budget = knapsack(batch['status'], total_budget, **kwargs), where batch['status'] contains the estimated success rates $\hat{p}_i$ for each prompt in the batch.

  2. Batch expansion (same as before, but with heterogeneous counts): The budget vector is expanded into indices: for each prompt $i$, its index is repeated budget[i] times. The resulting index list selects the corresponding prompts (with repetition) from the batch.

  3. Rollout balancing (new): The index list is randomly shuffled before being passed to the inference engine, implementing the job-level randomization described above.

  4. Status update (new): After rewards are computed and advantages estimated, the training dataset's per-prompt statistics (c_i and t_i counts) are updated with the current iteration's results. This feeds into the $\hat{p}_i$ estimates for the next epoch.

  5. Everything else unchanged: The actor model generates sequences as usual (actor.generate_sequences(gen_batch)), rewards are computed via the verifiable reward function (Equation 2), advantages are computed via GRPO (Equation 3), and the actor is updated via standard policy gradient.

The effective gradient ratio improvement is a diagnostic, not a training objective. It is crucial to understand that the knapsack optimizer maximizes $\sum_i \text{Value}(N_i, \hat{p}_i)$, NOT the effective gradient ratio directly. The effective gradient ratio increase (20–40% across models, Figure 6) is an emergent consequence of allocating more budget to prompts where mixed outcomes are likely. The value function, through its ProbNonZeroGradient term, naturally pushes allocations toward configurations that produce non-zero gradients, but it also considers the LEARNING VALUE of those gradients through the InfoGain term. This prevents the optimizer from achieving 100% effective gradient ratio by simply allocating all budget to prompts with $p_i \approx 0.5$ (which reliably produce gradients) while ignoring both very hard and very easy prompts—a degenerate solution that would maximize the ratio metric but minimize actual learning.

4. Key Insights and Innovations

Innovation 1: Treating Exploration Budgets as an Optimization Variable Rather Than a Fixed Hyperparameter

The paper's most fundamental contribution is not the knapsack formulation itself—which is a straightforward application of a classical operations research framework—but the shift in perspective that exploration budgets can and should be optimized as a centralized resource. Before this work, the exploration budget NN (the number of rollouts per prompt in each GRPO iteration) was treated as a fixed hyperparameter, chosen based on GPU memory constraints, throughput considerations, or simple heuristics. The field's implicit assumption was that NN is a training configuration—like learning rate or batch size—to be tuned once and held constant.

This paper reframes NN as a decision variable that should vary across prompts and across training iterations based on each prompt's current learning status. The intellectual move is recognizing that the total exploration budget ∑iNi=Ntotal\sum_i N_i = N_{\text{total}} is the true constraint (determined by available GPU hours), not the per-prompt budget NN. Once you accept this reframing, the natural question becomes: given a fixed total, how do you distribute it to maximize learning?—which is precisely the knapsack problem.

This is more than a computational trick; it is a diagnostic reframing that exposes the hidden cost of uniform allocation. Figure 2 and Figure 3 expose something the field implicitly knew but had not quantified: the effective gradient ratio languishes below 60% and decays to ~20% because uniform allocation over-explores already-solved prompts while under-exploring hard ones. Prior work responded to this observation by filtering prompts (Yu et al., 2025; Team et al., 2025) or improving gradient estimators (Li et al., 2024; Ahmadian et al., 2024)—both reactions that compensate for the allocation problem rather than solving it. By treating the allocation itself as the optimization target, the knapsack approach addresses the root cause: prompts don't produce gradients because they don't receive sufficient exploration, not because the gradient estimator is flawed.

The significance extends beyond GRPO. Appendix B sketches extensions to RLOO, ReMax, and REINFORCE by adapting the ProbNonZeroGradient term. This suggests the budget-as-optimization-variable perspective is algorithm-agnostic—a general principle for online RL with LLMs, not a GRPO-specific hack. The modular formulation (Value = ProbNonZeroGradient × InfoGain) cleanly separates the algorithm-specific gradient condition from the algorithm-agnostic learning potential, making the framework extensible.

The 2×2\times resource equivalence result (Figure 9)—where Knapsack-GRPO with half the total budget matches standard GRPO—converts this conceptual reframing into a concrete economic claim: for a fixed performance target, treating exploration as an optimization variable halves the required compute. This is a fundamental efficiency result, not an incremental improvement, because it changes the scaling relationship between compute and performance rather than shifting the curve by a constant factor.

Innovation 2: The Diagnose-Then-Allocate Structure: Separating Difficulty Estimation from Budget Assignment

The paper introduces a clean two-phase architecture: first estimate each prompt's difficulty (success rate), then solve an optimization problem to allocate budgets accordingly. This separation is deceptively simple but has important structural consequences that distinguish it from prior approaches.

Prior methods addressing data heterogeneity conflated diagnosis and action. DAPO's dynamic sampling (Yu et al., 2025) interleaves exploration and filtering: it repeatedly generates rollouts, checks whether prompts produce mixed rewards, and filters until enough "effective" prompts accumulate. This means the exploration budget spent on discarded all-positive or all-negative prompts is wasted—it contributes neither to gradient computation (the prompts are filtered) nor to difficulty estimation (the outcome was already predictable). Curriculum learning approaches (Chen et al., 2025; Sun et al., 2025) similarly mix diagnosis and action by selecting prompts based on heuristics computed from the same rollouts used for training.

The knapsack approach separates these concerns. The previous epoch's rollouts serve only to estimate p^i\hat{p}_i, after which the knapsack solver determines allocations before any rollout generation occurs in the current epoch. This means every generated rollout in the current epoch contributes to gradient computation—there is no wasted exploration for filtering or diagnosis. The estimation cost is amortized across the entire previous epoch's training, making it effectively free in the marginal sense (the rollouts would have been generated anyway for training).

This separation also makes the approach algorithmically clean and implementationally minimal. The knapsack solver's only inputs are the success rate estimates and the total budget—it requires no modification to the RL algorithm, no additional hyperparameters, and no changes to the inference or training infrastructure beyond the budget assignment step (Listing 1). This is not merely a convenience; it reflects a genuine architectural insight that difficulty estimation and budget allocation are separable subproblems that can be optimized independently.

The downside, which the paper acknowledges, is staleness: the previous epoch's p^i\hat{p}_i is an approximation of the current policy's true pip_i. The empirical results (Figures 6–8, Table 2) suggest this staleness is acceptable for MATH reasoning with these model scales, but it represents a tradeoff between estimation accuracy and implementation simplicity. The paper's framing of this as an "exploration-exploitation tradeoff" (Section 3.2) is apt: the first epoch uses homogeneous allocation for pure exploration, after which the system exploits the collected statistics for optimized allocation. Future work on online difficulty estimation could close the staleness gap while maintaining the separation of concerns.

Innovation 3: A Value Function That Couples Exploration Feasibility with Learning Potential

The paper's value function Value(N_i, p_i) = ProbNonZeroGradient(N_i, p_i) × InfoGain(p_i) is the intellectual engine of the allocation framework, and its design embodies a substantive claim about what makes exploration valuable that goes beyond obvious definitions.

The key insight is the multiplicative coupling. ProbNonZeroGradient alone would correctly identify that hard prompts need large budgets to produce gradients, but would naively allocate maximum budget to the hardest prompts regardless of whether those gradients would actually improve the model. InfoGain alone would correctly identify that intermediate-difficulty prompts are most improvable, but would ignore whether the allocated budget is sufficient to actually produce a gradient. The product ensures that budget flows to prompts that are both explorable AND improvable—a conjunction that neither term alone captures.

The InfoGain(p_i) ≈ p_i(1 - p_i)^2 approximation, derived from a first-order Taylor expansion of policy gradient updates (Proposition 1), is not merely a convenience—it encodes a specific hypothesis about where learning happens. The approximation predicts that learning potential peaks at pi=1/3p_i = 1/3, decays to zero at both extremes, and (the paper claims) exhibits asymmetry favoring harder prompts over easier ones at equal distance from the optimum. This is an empirically testable claim about the relationship between current performance and improvability. If it were wrong—if, for example, learning potential were monotonic in difficulty—the allocation would be systematically biased. The paper's strong empirical results (2–4 point average gains, Figure 9's 2×2\times efficiency) provide indirect validation, and the synthetic experiment in Figure 10 provides direct validation of the approximation's accuracy against exact gradient updates.

The conceptual contribution is making "learning value" computable from a single scalar statistic (the success rate) that the training loop already collects. Prior work on exploration in RL—whether intrinsic motivation, curiosity-driven exploration, or information-theoretic objectives—typically requires auxiliary models, density estimators, or complex credit assignment. This paper shows that for the specific setting of GRPO with verifiable rewards, a simple function of the success rate suffices. This is a domain-specific insight: the structure of the GRPO gradient estimator (zero when all rewards are identical) and the verifiable reward setting (binary outcomes) create a situation where the key exploration statistic is trivially available, and the paper exploits this structure rather than fighting it.

The modularity of the value function is a deliberate design choice with forward-looking implications. By separating ProbNonZeroGradient (algorithm-specific) from InfoGain (algorithm-agnostic), the framework invites future work to plug in richer InfoGain formulations—perhaps incorporating response length, reasoning diversity, or learned value functions—without changing the allocation mechanics. The paper flags this explicitly in Section 7 ("Designing richer value functions") and positions the current p(1−p)2p(1-p)^2 formulation as a starting point, not a final answer.

Innovation 4: Empirical Evidence That Reallocation—Not Additional Compute—Solves the Exploration Bottleneck for Many Prompts

The paper's most practically significant finding is that the exploration bottleneck for hard prompts can often be resolved by reallocating existing compute from easy prompts, without increasing the total budget. This is not an obvious or inevitable result. It could have been the case that all prompts genuinely need N≥8N \ge 8 rollouts, or that the hardest prompts are fundamentally unsolvable regardless of budget. The paper's experiments demonstrate a more nuanced reality.

Figure 5 reveals that the knapsack allocator can assign up to 93 rollouts to individual prompts within the same total budget (Ntotal=2048N_{\text{total}} = 2048) that uniform allocation distributes as N=8N = 8 across all prompts. This is possible because many prompts have become trivially easy (pi≈1.0p_i \approx 1.0)—at which point they need only the minimum budget (Nlow=2N_{\text{low}} = 2) to verify continued mastery. The "savings" from these easy prompts are redirected to the hard ones, creating effective exploration budgets that would be economically prohibitive to achieve uniformly (a uniform N=93N = 93 would require 256×93≈23,808256 \times 93 \approx 23,808 rollouts, roughly 11.6×11.6\times the standard budget).

The transition matrix (Figure 7) provides the causal evidence that this reallocation works: Knapsack-GRPO reduces the self-absorption rate of extremely-hard prompts from 47.1% to 43.4%, and increases transitions from hard categories to extremely-easy. The 197-prompt reduction in the extremely-hard category (Figure 8, from 3,793 to 3,596) represents prompts that were essentially unlearnable under uniform allocation but became tractable when given sufficient exploration budget to encounter at least one successful trajectory.

However, the paper is appropriately cautious about the limits of this finding. Approximately 20% of prompts remain extremely-hard even after 1,000 iterations with Knapsack-GRPO, and the authors note that 577 of these recorded at least one positive trajectory during optimization—implying they are not inherently unsolvable, just insufficiently explored. This reveals a boundary condition: budget reallocation amplifies existing learning capacity but does not create it from nothing. Prompts for which the model's true pip_i is effectively zero (the policy assigns negligible probability to correct reasoning paths) cannot be rescued by any finite exploration budget, because ProbNonZeroGradient approaches zero regardless of NiN_i when the per-sample success probability is vanishingly small. The reallocation strategy helps prompts that are hard but feasible—those where the model occasionally stumbles upon a correct solution if given enough attempts—but not prompts that are genuinely beyond the model's current capability.

This finding connects to broader questions about the limits of online RL for LLMs: can self-play alone solve arbitrarily hard reasoning problems, or is there a fundamental capability threshold that requires better pretraining or architectural improvements? The paper's data suggests the latter—the persistent ~20% of extremely-hard prompts may represent problems the Qwen2.5-Math-7B model simply cannot reason about, regardless of exploration budget. The knapsack framework cannot answer this question definitively (it only allocates budget, it doesn't change the model's fundamental capability), but it provides the diagnostic tools to ask the question by distinguishing between "hard because underexplored" and "hard because infeasible."

5. Experimental Analysis

Evaluation Methodology

  • Dataset. All experiments use the DAPO-Math-17K dataset (Yu et al., 2025), which comprises 17,917 prompts, each paired with a ground-truth answer for verifiable reward computation (Section 5.1, Appendix C). The MATH benchmark is used for evaluation (Table 2), along with AIME (2024 and 2025 editions combined), AMC, MINERVA, OLYMPIAD Bench, and GPQA as out-of-domain scientific reasoning evaluation. For AIME, the authors combine the 2024 and 2025 editions into a single dataset due to small sample size. During training evaluation, models are assessed every 10 iterations using 16 generated responses, with 100 evaluation samples randomly selected when the total number exceeds this threshold (Appendix C).

  • Base model(s). Four Qwen-series models spanning 1B to 7B parameters and both pre-trained and instruction-tuned variants: DPSK-R1-Distill-1.5B (DeepSeek-R1-Distill-Qwen-1.5B, Guo et al., 2025), Qwen3-4B-Base, Qwen3-4B-Instruct-2507, and Qwen2.5-Math-7B (Yang et al., 2024, 2025). The paper states these models are chosen to demonstrate generality across model scales and training paradigms. DPSK-R1-Distill-1.5B uses 8K token maximum sequence length during training to accommodate its longer chain-of-thought outputs; other models use 4K tokens (Appendix C). Final evaluation uses different maximum sequence lengths per model (4K for Qwen2.5-Math-7B, 8K for Qwen3-4B variants, 16K for DPSK-R1-Distill-1.5B) to prevent response truncation, which means final results may not perfectly align with training curves (Appendix C).

  • Metrics. The primary training diagnostic is the effective gradient ratio, defined in Equation 4 as the fraction of individual generated samples that contribute non-zero gradients: effective-gradient-ratio = (1 / (M · N)) · Σ_i Σ_j 𝕀(g_{i,j} ≠ 0), where g_{i,j} is the gradient contribution from the j-th sample of the i-th prompt. Two complementary metrics are tracked: zero-gradient-ratio (by all positive rewards) — the proportion of prompts yielding zero gradients because all N responses are correct; and zero-gradient-ratio (by all negative rewards) — the proportion yielding zero gradients because all N responses are incorrect (Section 3.1, Figure 2). For downstream evaluation, the primary metric is accuracy (avg@16) — the fraction of evaluation problems solved correctly, averaged over 16 generated responses per problem (Table 2). The paper also reports prompt status distributions (Figure 8) categorizing training prompts into five bins based on success rate p_i: extremely-hard (p_i = 0), hard (0 < p_i ≤ 0.2), medium (0.2 < p_i < 0.8), easy (0.8 ≤ p_i < 1.0), and extremely-easy (p_i = 1.0). Transition matrices (Figure 7) track how prompts move between these categories during training.

  • Baselines. The primary baseline is standard GRPO (Shao et al., 2024) with uniform exploration budget allocation (N = 8 rollouts per prompt, M = 256 prompts per batch, total budget N_total = 2048). The paper also compares against GRPO combined with dynamic sampling from DAPO (Yu et al., 2025) in Appendix D.4 (Figures 18–19). Dynamic sampling repeatedly generates rollouts, filters prompts that yield only positive or only negative rewards, and accumulates "effective" prompts until a target batch size is reached. The comparison is made both in terms of exploration iterations (total computation spent) and gradient update iterations (number of parameter updates). For the ablation of Knapsack-GRPO variants, the paper includes Knapsack-GRPO without fallback strategy and Knapsack-GRPO with modified bounds (N_low = 0, N_up = 32) in Appendix D.3 (Figures 16–17).

  • Generation budget / compute accounting. In the main experiments (Section 5.1), the total exploration budget is fixed at N_total = 2048 rollouts per iteration, matching the uniform M = 256 prompts × N = 8 rollouts of standard GRPO. For the budget-scaling experiments (Section 5.3, Figure 9), the authors explore N_total = 1024 (equivalent to N = 4 in uniform GRPO) and N_total = 4096 (equivalent to N = 16). The paper reports training cost in A100 GPU hours: training Qwen2.5-Math-7B for 1,000 iterations requires approximately 1,400 GPU hours (Section 5.1). The knapsack solver itself adds "negligible overhead," running in 1–2 seconds with Numba acceleration (Section 4.2). The difficulty estimation cost is amortized across the previous epoch's training data and requires no additional generation beyond what standard GRPO already performs.

  • Cross-validation / statistical protocol. The paper does not report confidence intervals or statistical significance tests. The difficulty estimation uses the previous epoch's empirical success rates p̂_i = c_i / t_i as estimates for the current epoch (Section 4.2). The first epoch uses homogeneous allocation to collect initial statistics. For the final evaluation (Table 2), performance is reported as a single accuracy number per model-benchmark pair, averaged over 16 generated responses per evaluation problem. Training curves (Appendix D.2, Figures 12–15) report evaluation performance every 10 iterations, showing the trajectory but without error bars. The transition matrix analysis (Figure 7) and prompt status distributions (Figure 8) are computed over the full set of 17,917 training prompts, providing population-level statistics rather than sample estimates. The absence of uncertainty quantification means that the reported 2–4 point average improvements and the ~2× resource equivalence should be interpreted as point estimates without statistical guarantees—a limitation given the moderate test set sizes (AIME's combined pool is small, and many benchmarks are subsampled to 100 examples for evaluation).

Main Quantitative Results

Effective Gradient Ratio Improvements

The paper's central diagnostic metric—the effective gradient ratio—shows consistent and substantial improvements across all tested models when comparing Knapsack-GRPO to standard GRPO (Figure 6). For DPSK-R1-Distill-1.5B (Figure 6a), Knapsack-GRPO maintains the effective gradient ratio between approximately 60–70% throughout most of training, compared to GRPO which starts around 60% but declines to roughly 50% by iteration 1000. For Qwen3-4B (Figure 6b), Knapsack-GRPO sustains the ratio between roughly 55–75%, while GRPO fluctuates between 40–60% and shows a declining trend. For Qwen2.5-Math-7B (Figure 6c), Knapsack-GRPO maintains approximately 50–65% through mid-to-late training, compared to GRPO which drops from roughly 65% in early training to around 20% by iteration 1000. The paper quantifies this as a 20–40% improvement across models (Section 5.2), noting that "unlike uniform allocation, the knapsack method avoids a clear decreasing trend"—a qualitative observation supported by the curves but not reduced to a single numeric metric.

The zero-gradient dynamics underlying these improvements are decomposed in Figure 2 for standard GRPO (Qwen2.5-Math-7B), revealing three distinct phases: early training (0–70 iterations) where nearly 95% of prompts yield all-negative rewards, mid-training (70–600 iterations) where the effective ratio stabilizes above 40%, and late training (600+ iterations) where all-positive rewards rise to ~40% while all-negative rewards persist at ~20%, driving the effective ratio down to ~20%. Knapsack-GRPO's improvements (Figure 6c) suggest it mitigates these phase-dependent failure modes, though the paper does not provide a phase-decomposed version of Figure 6 to confirm this directly—the claim is supported by the aggregate ratio curves rather than stratified analysis.

Downstream Benchmark Performance

Table 2 reports the avg@16 accuracy across six benchmarks for four models. The average across all benchmarks (rightmost column) shows Knapsack-GRPO consistently outperforming GRPO: +3.8 points for DPSK-R1-Distill-1.5B (49.7 vs. 45.9), +1.9 points for Qwen3-4B-Base (45.1 vs. 43.2), +2.7 points for Qwen3-4B-Instruct (61.9 vs. 59.2), and +2.3 points for Qwen2.5-Math-7B (47.5 vs. 45.2). These averages mask substantial variance across benchmarks:

  • AIME: The largest absolute gain is +6.4 points for DPSK-R1-Distill-1.5B (34.0 vs. 27.6). Qwen3-4B-Base shows only +0.1 (20.8 vs. 20.7), Qwen3-4B-Instruct shows +1.2 (48.2 vs. 47.0), and Qwen2.5-Math-7B shows +0.4 (24.3 vs. 23.9). The inconsistency—with DPSK-R1-Distill-1.5B gaining substantially while other models show minimal gains—suggests the benefits may depend on model-specific factors (chain-of-thought length, base capability level).

  • AMC: The largest gains are +9.1 for Qwen3-4B-Base (66.0 vs. 56.9) and +6.8 for Qwen2.5-Math-7B (77.4 vs. 70.6). DPSK-R1-Distill-1.5B shows +4.0 (75.1 vs. 71.1). Qwen3-4B-Instruct shows a slight regression: -1.8 (83.1 vs. 84.9). This regression—Knapsack-GRPO performing worse than GRPO on an already-strong model on a specific benchmark—receives no specific discussion in the paper.

  • MATH: Gains are modest but consistent: +2.7 for DPSK-R1-Distill-1.5B (86.7 vs. 84.0), +0.4 for Qwen3-4B-Base (81.0 vs. 80.6), 0.0 for Qwen3-4B-Instruct (92.5 vs. 92.5), +2.2 for Qwen2.5-Math-7B (83.9 vs. 81.7). The saturation of Qwen3-4B-Instruct at 92.5 suggests a ceiling effect—when accuracy is already very high, the knapsack approach has limited room to improve.

  • MINERVA: Gains are +0.9 for DPSK-R1-Distill-1.5B (28.5 vs. 27.6), +3.8 for Qwen3-4B-Base (35.7 vs. 31.9), -3.6 for Qwen3-4B-Instruct (38.2 vs. 41.8), +0.9 for Qwen2.5-Math-7B (34.5 vs. 33.6). The -3.6 point regression for Qwen3-4B-Instruct on MINERVA, combined with the AMC regression, suggests this model may be particularly sensitive to the exploration allocation strategy, potentially because its instruction-tuned prior changes the relationship between success rate and learning value.

  • OLYMPIAD: Gains are +3.3 for DPSK-R1-Distill-1.5B (49.7 vs. 46.4), +1.3 for Qwen3-4B-Base (46.2 vs. 44.9), +1.7 for Qwen3-4B-Instruct (63.5 vs. 61.8), +2.2 for Qwen2.5-Math-7B (44.1 vs. 41.9).

  • GPQA (out-of-domain): Gains are +3.6 for DPSK-R1-Distill-1.5B (40.3 vs. 36.7), -1.1 for Qwen3-4B-Base (45.5 vs. 46.6), +5.5 for Qwen3-4B-Instruct (59.9 vs. 54.4), +3.0 for Qwen2.5-Math-7B (43.8 vs. 40.8). The out-of-domain nature of GPQA tests whether the knapsack-based exploration transfers to scientific reasoning; the mixed results (including the -1.1 regression for Qwen3-4B-Base) suggest transfer is not guaranteed.

Averaging the per-model gains across benchmarks and then averaging across models yields a ~2.7 point average improvement, consistent with the paper's "2-4 points" claim. However, the standard deviation across benchmark-model pairs is substantial—gains range from -3.6 to +9.1—indicating that the benefit is highly context-dependent rather than uniformly reliable.

Exploration Budget Distribution

Figure 5 visualizes the per-prompt exploration budgets allocated by Knapsack-GRPO across all training iterations for Qwen2.5-Math-7B. The distribution is heavily right-skewed: the maximum budget allocated to a single prompt in a single iteration reaches 93 rollouts, while the frequency histogram (log-scale y-axis) shows that the vast majority of allocations cluster at lower values. The paper does not report the mean, median, or standard deviation of this distribution, nor does it report the fraction of prompts receiving budgets above various thresholds (e.g., >8, >16, >32). The key qualitative claim—that the knapsack can "dynamically assign up to 93 exploration budgets to certain tasks" while noting "this level of dynamic, high-budget allocation is impractical to achieve under a conventional homogeneous budget allocation framework"—is visually supported by Figure 5. However, the paper does not provide the cost-equivalent analysis: what uniform N would be required to match the maximum budget of 93? The answer (as computed earlier: N = 93 uniform across all prompts would require ~11.6× the total budget) is not stated in the paper.

Prompt Status Transitions and Final Distributions

Figure 7 presents 5×5 transition matrices showing how prompts' difficulty categories evolve from initial status (before training) to final status (after training) for Qwen2.5-Math-7B under GRPO (Figure 7a) and Knapsack-GRPO (Figure 7b). The key differences are:

  • Extremely-hard self-absorption: 43.4% of initially extremely-hard prompts remain extremely-hard under Knapsack-GRPO vs. 47.1% under GRPO. This 3.7 percentage point reduction represents a ~7.9% relative improvement in escaping the extremely-hard category.
  • Transitions to extremely-easy (last column): Knapsack-GRPO shows consistently higher transition rates from all initial categories to the extremely-easy category. For initially hard prompts: 48.6% (Knapsack) vs. 42.0% (GRPO). For initially medium: 72.1% vs. 66.1%. For initially easy: 90.9% vs. 87.6%. For initially extremely-easy: 95.2% vs. 93.5%. This uniform upward shift suggests Knapsack-GRPO accelerates learning across the difficulty spectrum, not just for the hardest prompts.
  • Transition rates from extremely-easy: Both methods show high retention of extremely-easy prompts (93.5% GRPO, 95.2% Knapsack), but Knapsack-GRPO shows slightly lower reversion rates—2.5% drop to extremely-hard vs. 5.5% for GRPO, suggesting that maintaining minimum exploration budgets on solved prompts helps prevent catastrophic forgetting.

Figure 8 translates these transition dynamics into absolute counts. After training, Knapsack-GRPO has 3,596 extremely-hard tasks vs. 3,793 for GRPO—a reduction of 197 prompts (5.2% relative). Knapsack-GRPO has 9,274 extremely-easy tasks vs. 8,676 for GRPO—an increase of 598 prompts (6.9% relative). The middle categories (hard, medium, easy) show corresponding shifts: Knapsack-GRPO has fewer hard (306 vs. 549), fewer medium (2,591 vs. 2,902), and more easy (2,150 vs. 1,997) prompts.

The paper's observation that "approximately 20% of prompts remain in the extremely-hard category even after 1,000 training iterations" is supported: 3,596 / 17,917 ≈ 20.1% for Knapsack-GRPO, 3,793 / 17,917 ≈ 21.2% for GRPO. The follow-up finding that "577 of these challenging prompts recorded at least one positive trajectory during optimization" for Knapsack-GRPO (Section 5.2) is notable—it suggests that ~16% of the extremely-hard prompts (577 / 3,596) are explorable (the model can occasionally solve them) but have not been converted to consistently solvable through RL training. The paper does not report the analogous statistic for GRPO, preventing comparison.

Budget Scaling Experiments

Figure 9 compares Knapsack-GRPO and GRPO at three total exploration budgets (1,024, 2,048, and 4,096) for Qwen2.5-Math-7B, measured by average accuracy across the six benchmarks (avg@16). The key findings:

  • At N_total = 1024 (equivalent to N = 4 uniform), Knapsack-GRPO achieves 45.5 avg@16 vs. GRPO's 39.8—a +5.7 point advantage.
  • At N_total = 2048 (N = 8), Knapsack-GRPO achieves 47.5 vs. GRPO's 45.2—a +2.3 point advantage (matching Table 2).
  • At N_total = 4096 (N = 16), Knapsack-GRPO achieves 49.5 vs. GRPO's 47.8—a +1.7 point advantage.

The key economic claim: "Knapsack-GRPO clearly outperforms GRPO, particularly when computational resources are limited" (Section 5.3). The +5.7 gain at N_total = 1024 is the most striking, and the observation that "Knapsack-GRPO with a total budget of 1,024 achieves roughly the same average benchmark performance as standard GRPO with a total budget of 2,048" is the basis for the ~2× resource equivalence claim: 45.5 (Knapsack at 1,024) ≈ 45.2 (GRPO at 2,048). However, the paper does not compute the precise equivalence point—45.5 is slightly above 45.2, meaning the equivalence is approximate.

The diminishing gap at higher budgets (+2.3 at 2,048, +1.7 at 4,096) suggests that the benefits of heterogeneous allocation are largest when total compute is scarce relative to the exploration demands of hard prompts. When the uniform budget is already large (N = 16), most prompts receive sufficient exploration under both methods, reducing the relative advantage of knapsack reallocation. The paper does not discuss this interpretation or extrapolate to even larger budgets.

Comparison with Dynamic Sampling

Appendix D.4 (Figures 18–19) compares four configurations on Qwen2.5-Math-7B: GRPO, Knapsack-GRPO, GRPO + Dynamic Sampling, and Knapsack-GRPO + Dynamic Sampling, using two different x-axis metrics.

By exploration iterations (Figure 18): This metric measures performance against the total number of exploration rollouts generated, directly comparing computational efficiency.

  • Dynamic Sampling alone improves GRPO's average from 45.2 to 46.2 (+1.0).
  • Knapsack-GRPO alone achieves 47.5 (+2.3 over GRPO, +1.3 over Dynamic Sampling).
  • The combination Knapsack-GRPO + Dynamic Sampling achieves 46.5—better than Dynamic Sampling alone (+0.3) but worse than Knapsack-GRPO alone (-1.0).

The paper attributes this to Knapsack-GRPO "utilizing more gradient iterations" when dynamic sampling is not applied—dynamic sampling filters prompts until a target number of effective prompts is accumulated, which can require multiple exploration rounds per gradient update, reducing the number of gradient steps for a fixed exploration budget. Knapsack-GRPO, by contrast, uses ALL exploration to directly generate gradient updates, achieving more parameter updates per exploration unit.

By gradient update iterations (Figure 19): This metric measures performance against the number of model parameter updates, assessing the value of each gradient step rather than computational efficiency. The paper observes that "effective gradients, whether from dynamic sampling or our knapsack-based exploration, lead to greater performance gains for the same number of update iterations." This validates the underlying motivation—eliminating zero-gradient updates improves per-step learning—but does not establish superiority of either method for this metric.

The paper's conclusion—that these approaches are "parallel and can be combined"—is empirically supported by the combination outperforming GRPO (46.5 vs. 45.2), but the fact that Knapsack-GRPO alone outperforms the combination suggests interaction effects that are not fully understood. The paper does not investigate why adding dynamic sampling to Knapsack-GRPO degrades performance relative to Knapsack-GRPO alone.

Ablation Studies and Robustness Checks

Fallback strategy removal (Figure 16): Removing the fallback strategy that reallocates excess budget from solved prompts to extremely-hard prompts leads to "unstable training, large performance fluctuations on benchmarks such as AMC and OlympiadBench, and overall degraded results" for Qwen2.5-Math-7B. The training curves show Knapsack-GRPO without fallback underperforming the full Knapsack-GRPO across all six benchmarks, with particularly visible divergence on AMC (oscillating between ~55–70% vs. a steady climb to ~77% with fallback) and OLYMPIAD (erratic fluctuations vs. steady improvement). The paper's explanation—that without fallback, "unsolved tasks receive too few resources while easy prompts are oversampled"—is supported by the concrete example in Table 3, where the prompt with p_i = 0.0 receives 2 rollouts without fallback vs. 29 with fallback.

Bound hyperparameters N_low and N_up (Figure 17): Two ablations are tested against the default Knapsack-GRPO configuration (N_low = 2, N_up = 128): setting N_low = 0 (no minimum per-prompt budget) and setting N_up = 32 (restricted maximum budget). The N_low = 0 ablation performs worse than the default across most benchmarks, though the paper does not quantify the degradation. This supports the design rationale that a minimum budget maintains coverage and detects regression on previously-solved prompts. The N_up = 32 ablation also degrades performance, confirming that the ability to allocate up to 93 rollouts to extremely hard prompts (Figure 5) is important—capping the maximum at 32 prevents the large-budget exploration that the knapsack framework is designed to provide. The paper notes that "its specific value does not critically impact performance" for N_up = 128 vs. higher values, and the bound primarily exists "to facilitate faster computation of the knapsack optimization using dynamic programming."

Success rate estimation from previous epoch: The paper does not conduct a formal ablation comparing different estimation methods (e.g., exponential moving average vs. epoch-based, different epoch lengths, or ground-truth p_i from exhaustive sampling). The implicit validation comes from the overall performance gains (Table 2) and the similarity between the two-fold cross-validation results and the full-set results. However, the absence of an ablation on estimation quality means we cannot distinguish whether the knapsack framework's success is primarily due to the allocation optimization or the success-rate estimation—or whether better estimation could yield further gains.

Model scale and type robustness: The four tested models span different scales (1.5B, 4B, 7B) and types (pre-trained, instruction-tuned, math-specialized, distilled), and Knapsack-GRPO improves average performance for all of them (Table 2), suggesting the method is robust to these variations. However, the benchmark-level regressions (Qwen3-4B-Instruct on AMC: -1.8, on MINERVA: -3.6; Qwen3-4B-Base on GPQA: -1.1) indicate that robustness is not universal—the method can degrade performance on specific benchmark–model combinations. The paper does not investigate these regressions or provide diagnostic analysis.

Training duration: All main experiments use 1,000 training iterations. The paper does not report results at intermediate checkpoints (e.g., 500 iterations) to assess whether the benefits saturate or continue to accumulate. The training curves (Appendix D.2, Figures 12–15) show performance trajectories but do not include early-stopping analysis. The effective gradient ratio curves (Figure 6) suggest that Knapsack-GRPO's advantage is maintained or widens in late training, but the paper does not test whether extending training beyond 1,000 iterations would further benefit Knapsack-GRPO (whose effective gradient ratio remains high) relative to GRPO (whose effective gradient ratio declines).

Dataset ablation: All experiments use DAPO-Math-17K for training. The paper does not test on alternative RL training datasets (e.g., different problem distributions, different difficulty compositions, or non-math domains) to assess whether the knapsack approach's benefits depend on the specific difficulty distribution of the training data. This is a significant gap, as the theoretical analysis (Theorem 1, Figure 3) predicts that the benefits depend on the distribution of p_i across prompts—a dataset with uniformly easy or uniformly hard prompts would provide less opportunity for beneficial reallocation than DAPO-Math-17K's heterogeneous difficulty distribution.

Missing ablation: alternative value functions. The paper uses Value(N_i, p_i) = ProbNonZeroGradient(N_i, p_i) × InfoGain(p_i) with InfoGain ≈ p_i(1 - p_i)^2. No ablation compares this against alternative formulations—e.g., using only ProbNonZeroGradient (which would maximize gradient probability without considering learning value), using only InfoGain (which would allocate to intermediate-difficulty prompts regardless of exploration feasibility), or using a uniform value function (which would reduce to homogeneous allocation). These ablations would clarify which component of the value function drives the observed gains.

Missing ablation: knapsack optimization vs. simpler heuristics. The paper uses dynamic programming to solve the exact knapsack problem. No ablation compares this against simpler allocation heuristics—e.g., allocating N_i proportionally to 1/(p_i(1-p_i)), or using a threshold-based rule (allocate maximum budget to prompts below a difficulty threshold, minimum to those above). Such ablations would clarify whether the formal optimization is necessary or whether simpler heuristics could achieve similar gains.

Critical Assessment

Do the experiments support the central claim that Knapsack RL "increases the effective ratio of non-zero policy gradients by 20–40% during training"?

Supported, but with measurement granularity caveats. Figure 6 shows the effective gradient ratio curves for three models, and the visual improvement over GRPO is clear. However, the paper never reduces the "20–40%" claim to a specific numeric computation—e.g., the improvement averaged over training, or at specific checkpoints. The curves show that the gap varies substantially over training (narrow in early iterations, widening in late training for Qwen2.5-Math-7B), making a single percentage range an oversimplification. More critically, the effective gradient ratio is a diagnostic metric, not a direct measure of learning—the paper does not establish a causal relationship between the ratio improvement and the downstream accuracy gains. It is possible that some of the accuracy gains come from other effects (e.g., more diverse rollouts on hard prompts providing better coverage of solution space) that are correlated with but not caused by the higher gradient ratio.

Do the experiments support the claim of "average improvements of 2–4 points and peak gains of 9 points on specific tasks"?

Supported, but the variance across benchmarks and models undercuts the reliability claim. Table 2 reports average gains of +1.9 to +3.8 across models, consistent with "2–4 points." The "peak gain of 9 points" is supported by the +9.1 improvement for Qwen3-4B-Base on AMC. However, the regressions on specific benchmarks—Qwen3-4B-Instruct on AMC (-1.8 points) and MINERVA (-3.6 points), Qwen3-4B-Base on GPQA (-1.1)—mean the method can also degrade performance. The paper does not discuss these regressions, their causes, or their frequency. A practitioner evaluating whether to adopt Knapsack RL would need to know not just the average gain but the probability of regression on their specific task distribution—information the paper does not provide.

Do the experiments support the claim that "achieving comparable performance with traditional homogeneous allocation would require about 2× the computational resources"?

Partially supported, with important caveats about the scope of the comparison. Figure 9 shows that Knapsack-GRPO at N_total = 1024 (45.5 avg@16) approximately matches GRPO at N_total = 2048 (45.2 avg@16), supporting the 2× claim for Qwen2.5-Math-7B. However, three factors limit the generality of this claim:

  1. Only one model tested: The budget scaling experiment (Figure 9) is conducted only on Qwen2.5-Math-7B. The paper does not demonstrate the 2× equivalence for the other three models (DPSK-R1-Distill-1.5B, Qwen3-4B-Base, Qwen3-4B-Instruct). Given the heterogeneous benchmark-level results, it is plausible that the resource equivalence ratio varies by model.

  2. The equivalence is approximate, not exact: 45.5 ≈ 45.2 is a 0.3 point difference, close enough for a practical claim, but the paper does not report the standard error of these averages (recall: avg@16 over benchmarks with variable sizes, some subsampled to 100 examples). Without error bars, we cannot assess whether 45.5 is statistically distinguishable from 45.2, or whether the equivalence could be stated as "1.8×" or "2.2×" with equal justification.

  3. The equivalence applies to the specific total budgets tested: The paper tests only three discrete budget levels (1,024, 2,048, 4,096). The 2× equivalence is inferred from the point where Knapsack-GRPO at 1,024 crosses GRPO at 2,048, but we don't know the shape of the curve between these points—the true equivalence might be at 1.7× or 2.3×. More budget levels would be needed to precisely characterize the scaling relationship.

Do the experiments support the claim that Knapsack RL is a "computational 'free lunch'"?

The core claim—no additional total exploration budget—is valid, but the analysis ignores two categories of hidden costs. The knapsack solver itself adds negligible overhead (1–2 seconds per iteration), and the success-rate estimation reuses data already collected during training. In this narrow sense, the method is free. However:

  1. The first epoch uses homogeneous allocation: The knapsack approach requires at least one epoch of uniform exploration to collect initial success rate estimates. This means there is a "cold start" period where no gains are realized, and the cumulative benefit over training must overcome this initial investment. The paper does not report cumulative performance over training iterations (e.g., area under the training curve), making it impossible to assess whether the method is a "free lunch" when considering the entire training run rather than just the final checkpoint.

  2. The method trades off between-prompt fairness for aggregate performance: By reallocating budget from easy prompts (which receive only 2 rollouts under Knapsack-GRPO) to hard prompts (which can receive up to 93), the method implicitly prioritizes learning on hard prompts at the potential expense of maintaining performance on easy ones. The transition matrix (Figure 7) shows slightly lower reversion from extremely-easy to easier categories under Knapsack-GRPO, but this is a distribution-level statistic—individual easy prompts might receive insufficient exploration and regress without detection. The "free lunch" framing assumes that maintaining easy-prompt performance with minimal budget is costless, which the Qwen3-4B-Instruct regressions on AMC and MINERVA call into question.

What experiments would have strengthened the paper but were not run?

1. Difficulty estimation quality ablation. The method's success depends critically on the accuracy of p̂_i estimates. A direct ablation comparing epoch-based estimation against ground-truth p_i (from exhaustive 256-sample estimation, as in Figure 3) would quantify how much the staleness and noisiness of empirical estimates limits performance. This would also clarify whether the method's ceiling is the knapsack optimization or the estimation quality.

2. Online vs. offline difficulty estimation. The current method uses previous-epoch estimates. An online variant that updates p̂_i within each iteration using exponential moving averages could potentially respond faster to changing difficulty. Comparing these approaches would illuminate the exploration-estimation tradeoff.

3. Domain transfer experiments. All training is on DAPO-Math-17K (math). The GPQA benchmark (scientific reasoning) provides some out-of-domain signal, but the mixed results (-1.1 to +5.5 across models) don't establish reliable transfer. Testing on a non-math RL training dataset (e.g., coding or agentic tasks) would establish whether the knapsack approach generalizes beyond math reasoning.

4. Training duration scaling. The paper trains for 1,000 iterations. Extending to 2,000 or 5,000 iterations would test whether Knapsack-GRPO's benefits compound or saturate, particularly given that the effective gradient ratio curves (Figure 6) suggest Knapsack-GRPO's advantage widens in late training.

5. Analysis of regression cases. The benchmark-level regressions (Qwen3-4B-Instruct on AMC and MINERVA, Qwen3-4B-Base on GPQA) are reported but not investigated. A diagnostic analysis of which prompts lost performance and why—e.g., were they extremely-easy prompts that received insufficient budget and regressed?—would clarify the failure modes and potentially suggest mitigation strategies.

6. Comparison against prompt-filtering methods at equal compute. The DAPO dynamic sampling comparison (Appendix D.4) shows Knapsack-GRPO outperforming dynamic sampling by exploration iterations, but the comparison is confounded by Knapsack-GRPO performing more gradient updates. A comparison at equal gradient updates AND equal total exploration budget would isolate the allocation benefit from the update-frequency benefit.

Do the experiments demonstrate that Knapsack RL enables learning on prompts that were "unlearnable" under uniform allocation?

Partially, with the evidence pointing to a real but bounded effect. The transition matrix (Figure 7) and prompt count shifts (Figure 8) demonstrate that Knapsack-GRPO converts more extremely-hard prompts to solvable categories than GRPO—a reduction of 197 prompts in the extremely-hard category. This is a genuine improvement but represents only 1.1% of the training set (197 / 17,917). The vast majority of prompts that end up in the extremely-easy category would likely have gotten there under GRPO as well—the 598-prompt increase in extremely-easy may partially reflect acceleration of prompts that were already on a trajectory to mastery. The finding that 577 of the remaining 3,596 extremely-hard prompts under Knapsack-GRPO recorded at least one success suggests headroom for further improvement, but also indicates that even with optimal allocation, ~16% of the hard-prompt population remains stubbornly difficult, succeeding occasionally but not reliably. This reveals a boundary condition: the knapsack approach helps hard prompts that are sporadically solvable (the model CAN produce a correct answer given enough attempts) but cannot help prompts where the model never generates a correct trajectory, because no budget finite enough to be practical can reliably produce a gradient for such prompts.

6. Limitations and Trade-offs

Limitation 1: The Difficulty Estimation Cost Is Not Accounted For, Making the "Free Lunch" Claim Conditional

The assumption or constraint. The entire knapsack framework depends on estimating each prompt's success rate $p_i$ from historical data. The paper uses the previous epoch's empirical success rates $\hat{p}_i = c_i / t_i$, and the first epoch must use homogeneous allocation to collect these initial statistics. The paper states (Section 3.2, Section 4.2):

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

and acknowledges this as an "exploration-exploitation tradeoff" where "compute spent assessing difficulty versus compute spent solving the problem" represents an unresolved tension.

The consequence. The headline claim of a computational "free lunch" (Section 5, Section 7) — that Knapsack-GRPO achieves ~2× resource equivalence without additional compute — is only true if you ignore the cold-start cost. During the first epoch, the system operates in uniform-allocation mode, deriving no benefit from the knapsack optimization while still consuming the full $N_{\text{total}} = 2048$ budget per iteration. For a typical 1,000-iteration training run with $\sim 70$ iterations per epoch, this means approximately 7% of the total training compute is spent in the initial uniform-allocation phase before the knapsack optimizer activates. For shorter training runs, this fraction would be proportionally larger — at 200 iterations, roughly 35% of total compute would be spent before any benefit is realized.

More subtly, the success rate estimates $\hat{p}_i$ are stale by one epoch, meaning the allocation decisions are always based on slightly outdated difficulty information. For rapidly changing policies (e.g., early training when the effective gradient ratio drops from 95% to 60% within 70 iterations, per Figure 2), the previous epoch's $\hat{p}_i$ may poorly reflect the current policy's true $p_i$, causing the knapsack optimizer to allocate budgets based on a difficulty landscape that no longer exists. The paper provides no analysis of the lag between estimated and true success rates over the course of training.

What evidence exists in the paper. There is no ablation comparing epoch-based estimation against ground-truth $p_i$ (from exhaustive sampling), and no analysis of how the discrepancy between $\hat{p}_i$ and true $p_i$ evolves over training. The paper's comparison of oracle vs. predicted difficulty bins (Figures 4 and 8 in the original test-time compute paper — note: this paper does not have an analogous oracle vs. predicted ablation; the success rate estimation is not compared against any ground truth). The strong downstream results (Table 2) provide indirect evidence that the estimation lag is tolerable, but they do not establish how much performance is left on the table by the staleness.

Mitigation status. The paper explicitly flags this as an area for future work (Section 7, "Designing richer value functions"), suggesting that "more sophisticated estimation techniques (e.g., online logistic regression) that account for task correlations present promising directions for future improvement." No partial mitigation is attempted — the system uses the simplest possible estimator (previous epoch's empirical average) and accepts the staleness as a known cost.

Limitation 2: Approximately 20% of Prompts Remain Unsolved Regardless of Allocation, Establishing a Hard Capability Ceiling

The assumption or constraint. The knapsack approach assumes that all prompts are solvable given enough exploration — that the true success rate $p_i > 0$ for every prompt, and the only barrier to learning is insufficient sampling. The paper's theoretical framework (Theorem 1, the value function) treats $p_i = 0$ prompts as requiring infinite exploration budget, and the fallback strategy allocates leftover budget to them as a heuristic workaround. The paper acknowledges (Section 5.2):

"Despite these promising results, approximately 20% of prompts remain in the extremely-hard category even after 1,000 training iterations."

and further notes that "577 of these challenging prompts recorded at least one positive trajectory during optimization, implying they are not inherently unsolvable" — meaning the remaining $\sim 3,000$ prompts (roughly 17% of the training set) never produced a correct response across all of training.

The consequence. The knapsack framework cannot help prompts where the model's policy places essentially zero probability mass on correct reasoning paths. For such prompts, no finite exploration budget can produce a non-zero gradient because $\text{ProbNonZeroGradient}(N_i, 0) = 0$ for any $N_i$. The value function correctly assigns zero value to these prompts (since $\text{InfoGain}(0) = 0$), and the fallback strategy allocates them leftover budget as a hail-mary — but if even 93 rollouts (the maximum observed in Figure 5) fail to find a correct trajectory, the prompt is effectively invisible to the learning process.

This creates a self-reinforcing failure mode: prompts the model genuinely cannot solve receive no useful gradients, so the model never improves on them, so they continue to receive no useful gradients. The knapsack framework amplifies learning on feasible prompts (those with $p_i > 0$) but cannot break through fundamental capability barriers — it does not change the model's underlying reasoning capacity, only how efficiently that capacity is deployed across the training set.

This is particularly consequential for online RL as a self-improvement paradigm. If the goal is to use RL to teach the model to solve problems it currently cannot solve (as opposed to refining performance on problems it can sometimes solve), the knapsack approach offers no leverage. The persistent ~20% of unsolved prompts represents a hard ceiling on what budget reallocation alone can achieve.

What evidence exists in the paper. Figure 8 shows 3,596 vs. 3,793 extremely-hard prompts remaining after training for Knapsack-GRPO and GRPO respectively — a difference of only 197 prompts out of 17,917 (1.1% of the training set). The transition matrix (Figure 7a vs. 7b) shows that Knapsack-GRPO reduces the extremely-hard self-absorption rate from 47.1% to 43.4% — a relative improvement but still leaving nearly half of initially extremely-hard prompts in that state. The finding that 577 of the remaining 3,596 prompts under Knapsack-GRPO recorded at least one success (Section 5.2) quantifies the headroom for further improvement, but also reveals that approximately 3,000 prompts never succeeded even once — establishing a practical lower bound on what the current model can achieve regardless of exploration budget.

Mitigation status. The paper does not attempt to solve the fundamentally-unsolvable prompt problem. It positions the knapsack framework as addressing exploration efficiency, not model capability, and acknowledges in the conclusion (Section 7) that "more sophisticated strategies — such as tree-based exploration inspired by Monte Carlo Tree Search" — might help on currently-unsolvable prompts. The current method's approach is purely allocative: it shifts compute to prompts that can benefit but does not change the generation process itself to make unsolvable prompts solvable.

Limitation 3: Single Training Dataset and Task Domain — Generalization to Non-Math, Non-Verifiable Reward Settings Is Unestablished

The assumption or constraint. All experiments use the DAPO-Math-17K dataset for training, consisting of math reasoning problems with ground-truth answers that enable binary verifiable rewards (Equation 2: $r(x, y) = \mathbf{1}[\text{answer is correct}]$). The mathematical structure of the value function — particularly InfoGain(p_i) \approx p_i(1-p_i)^2 derived from softmax policy gradient updates — and the ProbNonZeroGradient formulation that depends on GRPO's binary-reward structure make no inherent assumptions about task domain, but were validated only on math.

The paper acknowledges this implicitly by including GPQA (scientific reasoning) as the only out-of-domain evaluation, but GPQA is used for evaluation only — the models were never trained on GPQA-style data, so the benchmark tests transfer of math-learned reasoning, not the knapsack framework's performance when applied to non-math training data.

The consequence. A practitioner training on coding tasks, agentic tasks, open-ended dialogue, or any domain without clean binary verifiable rewards cannot assume the knapsack framework will transfer. Several specific concerns arise:

  • Non-binary rewards: The ProbNonZeroGradient formulation assumes rewards are binary (Definition 1: $r \in \{0, 1\}$). For continuous or multi-level rewards, the condition for a "zero gradient" under GRPO is more complex — it requires that all samples have IDENTICAL rewards, not just that they're all 0 or all 1. The probability of this occurring depends on the reward distribution's support and may be much lower than in the binary case, potentially reducing the benefit of exploration budget reallocation.

  • Different difficulty distributions: The DAPO-Math-17K dataset's difficulty distribution (which generates the $p_i$ distribution that drives the knapsack allocation) is unknown but likely heterogeneous, with a mix of easy, medium, and hard problems typical of competition math datasets. A training set consisting primarily of easy problems (where most prompts have $p_i \approx 1.0$) would leave little budget to reallocate — the knapsack optimizer would assign minimum budgets almost everywhere, reducing to near-uniform allocation. A dataset of uniformly impossible problems ($p_i \approx 0.0$) would make the framework useless. The method's benefit depends on there being both easy prompts to economize on AND hard-but-feasible prompts to invest in. The paper provides no guidance on what dataset characteristics are necessary for the approach to be beneficial.

  • Verifier quality: The binary reward function (Equation 2) assumes perfect verification — the ground-truth answer exactly determines correctness. In domains with noisy or approximate verifiers (e.g., learned reward models in RLHF, heuristic evaluations for code), the $p_i$ estimate conflates model capability with verifier reliability, potentially causing the knapsack to allocate budget to prompts that APPEAR improvable (intermediate $\hat{p}_i$) but where the reward signal is actually too noisy to learn from.

What evidence exists in the paper. The GPQA evaluation (Table 2) shows mixed transfer results: Knapsack-GRPO improves over GRPO by +3.6 points for DPSK-R1-Distill-1.5B, +5.5 for Qwen3-4B-Instruct, and +3.0 for Qwen2.5-Math-7B, but degrades by -1.1 for Qwen3-4B-Base. This is inconsistent and provides no clear signal about domain transfer. No experiments train on non-math data or use non-binary rewards. The six evaluation benchmarks are all mathematics or science QA — there is no evaluation on code generation, multi-turn dialogue, or agentic task completion.

Mitigation status. The paper does not claim generality beyond the math domain. The limitation is one of omission rather than failure — the paper simply does not test other domains. Section 7's future work suggests extension but provides no concrete path. A practitioner evaluating whether to apply Knapsack RL to a different domain would need to run their own validation experiments, as the paper provides no evidence to guide expectations.

Limitation 4: The Value Function's InfoGain Approximation Has Not Been Empirically Validated as an Accurate Proxy for Learning Value

The assumption or constraint. The entire allocation framework depends on the value function $\text{Value}(N_i, p_i) = \text{ProbNonZeroGradient}(N_i, p_i) \times \text{InfoGain}(p_i)$ where $\text{InfoGain}(p_i) \approx p_i(1-p_i)^2$ is derived from a first-order Taylor expansion of policy gradient updates under a softmax model with unit learning rate and unit advantage (Proposition 1, Appendix A). This approximation relies on several idealizations:

  • Small parameter updates: The first-order Taylor expansion is accurate only when parameter changes are small relative to the curvature of the policy. In practice, GRPO updates use learning rates of $10^{-6}$ (Appendix C) and advantage clipping between -5 and 5, but the effective update magnitude varies across prompts, layers, and training stages.

  • Softmax over discrete actions: The derivation models the policy as a softmax over $K$ discrete actions with logits $z_k$, but LLM policies operate over sequences of tokens with autoregressive structure. The "action space" is intractably large, and the mapping from logits to token probabilities involves softmax normalization at each step, not a single flat softmax.

  • Unit advantage assumption: The derivation assumes $A = 1$ for the correct action, but in GRPO the advantages are $(r(x_i, y_{ij}) - b_i) \cdot c_i$ normalized by the standard deviation within each prompt's response group. The effective advantage magnitude varies across prompts and samples.

  • Neglect of cross-terms: The derivation drops the $\sum_{k \neq y} p_k^2$ term as "second-order in the update magnitude," but this depends on the distribution of probability mass across incorrect actions. For a prompt where the model concentrates probability on one incorrect answer, $\sum_{k \neq y} p_k^2$ could be large.

Despite these idealizations, the paper states the approximation "captures essential intuitions while remaining simple to compute" (Section 4.1).

The consequence. If $\text{InfoGain}(p_i) \approx p_i(1-p_i)^2$ does not accurately reflect true learning value, the knapsack optimizer will systematically misallocate budget. Specific failure modes:

  • Over-allocation to $p_i \approx 1/3$ prompts if true InfoGain peaks elsewhere. The approximation predicts maximum learning value at $p_i = 1/3$. If the true relationship between success rate and improvability is different — for example, if harder prompts ($p_i < 0.2$) benefit more from gradient updates than the approximation predicts — the knapsack will under-allocate to hard prompts and over-allocate to medium ones.

  • The asymmetry claim may be incorrect. The paper asserts that "for equally distant values of $p_i$ from 1/3, harder tasks yield larger information gain than easier tasks" (Section 4.1). As the analysis in Section 4 noted, this claim does not hold for the first-order Taylor expansion of $p(1-p)^2$ at small distances $d$ from 1/3 — the easier prompt actually has higher InfoGain. If this asymmetry is incorrect, the knapsack's preference for harder prompts over equally-distant easier prompts is misaligned with true learning value.

  • No learning value for prompts near $p_i = 1.0$ or $p_i = 0.0$. The approximation predicts exactly zero InfoGain at the extremes, meaning the value function assigns zero value to exploring prompts the model always solves or never solves. This is the reason the fallback strategy is necessary (Section 4.2). If true learning value is non-zero at extremes — for example, if occasional failures on easy prompts provide important signal about where the model is overconfident — the knapsack framework would systematically under-explore these prompts.

What evidence exists in the paper. The only direct validation of the InfoGain approximation is the synthetic experiment in Appendix A (Figure 10), which compares the approximate formula against exact gradient updates in a 100-action softmax setting. The paper states the two curves "align closely across different success rates." However, this validation is in a toy setting that does not capture the complexity of autoregressive LLM policies, and the alignment is visual rather than quantitative — no correlation coefficient or error metric is reported. There is no ablation comparing the proposed value function against alternative formulations (e.g., constant InfoGain, monotonic InfoGain, or learned value functions). The strong downstream results (Table 2, Figure 9) provide indirect evidence that the value function is adequate, but they do not validate that $p(1-p)^2$ is the correct functional form — a different InfoGain function might produce even better allocations.

Mitigation status. The paper explicitly acknowledges this limitation in Section 7 ("Designing richer value functions") as an area for future work: "Exploring alternative formulations of value functions could yield more accurate assessments of learning potential and further enhance allocation strategies." No ablation studies or sensitivity analyses test how performance varies with different InfoGain formulations, so a practitioner cannot assess how critical the specific $p(1-p)^2$ choice is.

Limitation 5: Benchmark-Level Regressions Demonstrate the Method Can Degrade Performance on Specific Tasks, and No Diagnostic Framework Exists to Predict or Prevent This

The assumption or constraint. The knapsack approach assumes that reallocating exploration budget to maximize aggregate learning value (Equation 5) will improve or at least not harm performance across all prompts and downstream tasks. The value function's additive structure ($\sum_i \text{Value}(N_i, \hat{p}_i)$) treats each prompt's contribution as independent, and the optimization maximizes total value without constraints on per-prompt or per-task performance floors.

The consequence. Table 2 reveals several cases where Knapsack-GRPO performs WORSE than standard GRPO on specific benchmarks:

  • Qwen3-4B-Instruct on AMC: 83.1 vs. 84.9 with GRPO (-1.8 points)
  • Qwen3-4B-Instruct on MINERVA: 38.2 vs. 41.8 with GRPO (-3.6 points)
  • Qwen3-4B-Base on GPQA: 45.5 vs. 46.6 with GRPO (-1.1 points)

These regressions are not minor noise — the -3.6 point drop on MINERVA for Qwen3-4B-Instruct is comparable in magnitude to the average gains the method achieves on other model–benchmark pairs. A practitioner deploying Knapsack RL cannot know in advance whether their specific task will benefit or be harmed, because the paper provides no diagnostic framework for predicting which tasks are vulnerable to regression.

The likely mechanism for these regressions: the knapsack allocator shifts exploration budget away from prompts with $\hat{p}_i \approx 1.0$ (easy prompts, receiving minimum $N_{\text{low}} = 2$ budget) and toward prompts with intermediate or low $\hat{p}_i$. If the easy prompts include problems that are superficially solved but where the model's mastery is fragile — for example, problems the model solved correctly in the previous epoch through lucky guesses or brittle reasoning patterns — then reducing their exploration budget from $N = 8$ to $N_i = 2$ means the model rarely encounters counterexamples that would expose the fragility. Over time, this can lead to catastrophic forgetting on these prompts, which manifests as benchmark-level regression.

This is a fundamental tradeoff between exploration diversity and exploitation focus. The knapsack framework explicitly prioritizes prompts with intermediate $\hat{p}_i$ where gradients are expected to be most informative, but this comes at the cost of reduced monitoring of already-mastered prompts. The transition matrix (Figure 7b) shows that 2.5% of initially extremely-easy prompts drop to extremely-hard under Knapsack-GRPO vs. 5.5% under GRPO — suggesting Knapsack-GRPO actually REDUCES regression on easy prompts in aggregate. However, this aggregate statistic masks the possibility that regression is concentrated on specific prompt types or task categories that happen to appear disproportionately in certain evaluation benchmarks.

What evidence exists in the paper. The regressions are visible in Table 2 but receive NO discussion in the main text or appendix. The paper reports "average improvements of 2-4 points" but does not mention that these averages include negative values. The training curves (Figures 12–15 in Appendix D.2) show per-benchmark trajectories, but the paper does not analyze cases where Knapsack-GRPO's curve falls below GRPO's. The transition matrix analysis (Figure 7) addresses prompt-level regression but not benchmark-level aggregation effects. There is no analysis of whether the regressed benchmarks disproportionately sample from prompt categories that the knapsack under-explores.

Mitigation status. No mitigation is attempted or suggested. The paper does not propose a mechanism for detecting or preventing task-level regression, nor does it recommend monitoring specific benchmarks during training to catch regressions early. The $N_{\text{low}} = 2$ minimum budget provides a floor on per-prompt exploration, but this floor was chosen based on coverage considerations (preventing degenerate zero-allocation) rather than as a calibrated minimum to prevent forgetting. A practitioner concerned about task-level regression would need to implement their own monitoring and potentially increase $N_{\text{low}}$ at the cost of reduced budget for hard prompts.

Limitation 6: The Method Has Only Been Tested on Four Models From a Single Family (Qwen) at Modest Scales (≤7B Parameters)

The assumption or constraint. All experiments use Qwen-series models: Qwen3-4B-Base, Qwen3-4B-Instruct-2507, Qwen2.5-Math-7B, and DPSK-R1-Distill-1.5B (which is a DeepSeek-R1 model distilled into a Qwen-1.5B architecture). The paper states (Section 5.1): "We conduct experiments with both pre-trained and instruction-tuned models" and tests "Qwen series models sized from 1B to 7B," arguing this demonstrates "generality across model scales and training paradigms."

The consequence. Several aspects of the knapsack framework's effectiveness may depend on model-specific properties that the Qwen family shares but that do not generalize:

  • The relationship between success rate and learning value (InfoGain(p_i)). The $p(1-p)^2$ approximation is derived from softmax policy gradient dynamics under idealized conditions. Different model families (e.g., Llama, Mistral, Gemma) or architectures (dense vs. mixture-of-experts) may have different gradient response characteristics — for example, models with different attention patterns, normalization schemes, or parameter counts may exhibit different per-step improvement rates at a given success rate. If the true InfoGain function differs by model family, the knapsack's allocation would be misaligned.

  • The exploration cost structure. The autoregressive generation cost per rollout depends on model size, sequence length, and inference infrastructure. For larger models (e.g., 70B, 405B parameters), the generation cost dominates training cost much more heavily, potentially changing the cost–benefit calculus of allocating large exploration budgets to individual prompts. A 93-rollout allocation (as in Figure 5) for a 70B model would be proportionally far more expensive relative to the gradient computation cost than for a 7B model, potentially making the "free lunch" less free.

  • The effective gradient ratio dynamics. The zero-gradient patterns documented in Figure 2 and Figure 6 are specific to the interplay between the model's capability distribution and the DAPO-Math-17K dataset. A model with different initial capabilities — for example, a stronger model that starts with high $p_i$ on most prompts — would have a fundamentally different $\hat{p}_i$ distribution, potentially leaving less room for beneficial reallocation (if most prompts are already $p_i \approx 1.0$, the knapsack would allocate near-minimum budgets everywhere).

  • Base model vs. instruction-tuned vs. distilled models. The four tested models span different training paradigms, and the results show inconsistent patterns: the instruction-tuned Qwen3-4B-Instruct shows the largest benchmark-level regressions (AMC: -1.8, MINERVA: -3.6), while the base Qwen3-4B-Base and the distilled DPSK-R1-Distill-1.5B show more consistent improvements. This suggests the knapsack framework may interact differently with models that have undergone instruction tuning (which may change the relationship between success rate and learning dynamics), but the paper does not investigate this.

  • Scale extrapolation. The largest tested model is 7B parameters. The paper makes no claims about how the knapsack framework scales to 70B, 405B, or larger models. For very large models, the generation cost dominates the total training cost, and the 1–2 second knapsack solver overhead becomes even more negligible relative to per-iteration cost. However, the value function formulation — derived from small-update assumptions — may break down if larger models exhibit different learning dynamics per gradient step.

What evidence exists in the paper. The four models are all Qwen-based and span only a ~4.7× range in parameter count (1.5B to 7B). Table 2 shows consistent average improvements across all four models (+1.9 to +3.8 points), which supports the claim of within-family generality but does NOT establish cross-family transfer. The GPQA out-of-domain evaluation provides some signal of domain transfer but not of model-family transfer. The paper provides no analysis of how the $\hat{p}_i$ distribution or the relationship between $N_i$ and $\text{Value}(N_i, p_i)$ varies across the four models — it is possible that the same value function works for all four because they share architectural and training similarities.

Mitigation status. The paper does not claim cross-family generalization. The limitation is one of scope rather than failure — the experiments are thorough within the Qwen family but do not extend beyond it. A practitioner using a non-Qwen model would need to validate the approach from scratch, as the paper provides no evidence about transfer. The paper's extensibility discussion (Section 7, Appendix B) focuses on algorithmic extensions (to RLOO, ReMax, REINFORCE) rather than model-family extensions.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a new axis for optimization in LLM reinforcement learning — exploration budget allocation — that has been almost entirely overlooked in prior work. Before this paper, the dominant approaches to improving RL training efficiency addressed either which prompts to train on (curriculum learning, dynamic sampling) or how to use the gradients that were produced (variance reduction, improved baselines). The exploration budget $N$ — how many rollouts to generate per prompt — was treated as a fixed hyperparameter, chosen based on GPU memory constraints and held constant across all prompts and all training iterations. This paper demonstrates that $N$ should instead be a decision variable that varies per prompt based on the model's current learning status, and that optimizing this variable through a principled knapsack formulation yields efficiency gains comparable to doubling the total compute budget (Figure 9).

This reframing is more than a computational trick — it is a diagnostic intervention that exposes hidden waste in existing RL pipelines. The effective gradient ratio analysis (Figure 2, Figure 6) quantifies something practitioners have long suspected but never measured systematically: under uniform allocation, 40–80% of autoregressive generation produces zero learning signal because prompts receive either all-correct or all-incorrect responses. Prior work responded to this waste by filtering prompts (DAPO's dynamic sampling, Yu et al., 2025) or by improving gradient estimators (ReMax, RLOO) — both approaches that compensate for the allocation problem rather than solving it. By treating budget allocation itself as the optimization target, this paper addresses the root cause: prompts don't produce gradients because they receive insufficient exploration, not because the gradient estimator is flawed or the prompts are inherently unlearnable.

The paper resolves a tension between two common responses to exploration inefficiency. One school of thought (exemplified by DAPO and Kimi k1.5) advocates filtering out prompts that produce zero gradients, arguing that training on them wastes compute. The other school (exemplified by the broader RL tradition) argues that hard prompts are exactly where learning should happen — converting failures to successes is the point of RL. The knapsack framework reconciles these positions by showing they are both partially right. Filtering is appropriate for prompts that are fundamentally unsolvable (p_i effectively 0, where no finite budget will produce a gradient), but harmful for prompts that are hard but feasible (0 < p_i \ll 0.5, where sufficient exploration would reveal occasional successes). The framework provides a principled way to distinguish these cases — through the value function and the fallback strategy — rather than treating all zero-gradient prompts identically.

The paper also establishes verifier over-optimization as a first-class phenomenon in exploration budget allocation, though not by that name. The finding that InfoGain(p_i) \approx p_i(1-p_i)^2 peaks at p_i = 1/3 and decays to zero at both extremes means that the learning value of exploration is non-monotonic in difficulty — the hardest prompts are not necessarily the most valuable to explore. This parallels the test-time compute scaling literature (Snell et al., 2024), where verifier-guided search can harm performance on easy problems due to over-optimization, but it applies the insight to the training phase: allocating excessive budget to prompts near the extremes of the difficulty spectrum provides diminishing returns, not because exploration is infeasible (though it may be), but because the expected improvement per gradient step is small. This reframes exploration budget allocation as a problem of targeting the "improvable middle" — prompts where the model is uncertain enough to generate both successes and failures, but competent enough that gradient updates actually change behavior.

The research directions this work makes more attractive:

  • Allocation-aware RL algorithm design. The GRPO-specific ProbNonZeroGradient formulation and the algorithm-agnostic InfoGain decomposition (Appendix B) suggest a modular approach: future RL algorithms for LLMs could be designed with explicit consideration of how their gradient estimator interacts with exploration budget allocation, rather than treating exploration as a separate concern. Algorithms whose gradient condition is easier to satisfy (e.g., requiring only one success rather than mixed outcomes) would make the knapsack formulation simpler and potentially more effective.

  • Online difficulty estimation and dynamic allocation. The paper's epoch-based success rate estimation is deliberately simple, but the framework makes online estimation a natural next step — if \hat{p}_i can be updated within an epoch, the knapsack solver could run more frequently, reducing staleness and potentially responding to rapid policy changes in early training.

  • Scaling laws for exploration compute. The budget scaling experiment (Figure 9) hints at a relationship between total exploration budget and performance that differs between uniform and knapsack allocation. Systematically characterizing this relationship — how does the knapsack advantage scale with total budget, model size, and dataset difficulty distribution? — would provide guidance for practitioners allocating training compute.

The research directions this work makes less attractive:

  • Purely uniform exploration scaling. The finding that Knapsack-GRPO with half the budget matches GRPO (Figure 9) casts doubt on the cost-effectiveness of simply increasing N uniformly as a strategy for improving RL training. Unless the uniform budget is already extremely small, the knapsack approach dominates.

  • Prompt filtering as a standalone solution. The comparison with dynamic sampling (Appendix D.4) shows Knapsack-GRPO outperforming filtering-based approaches when measured by exploration iterations, because filtering discards compute spent on prompts that are subsequently excluded from the gradient update. The knapsack approach, by contrast, ensures every generated rollout contributes to some gradient update. This doesn't make filtering obsolete — it can still be complementary (as the combination experiments show) — but it suggests filtering alone leaves significant efficiency on the table.

Follow-Up Research This Work Enables

Online difficulty estimation with exponential moving averages vs. epoch-based stale estimates. The current method uses the previous epoch's empirical success rates \hat{p}_i = c_i / t_i, introducing a lag of up to one full epoch (~70 iterations). This staleness is acknowledged as a limitation but never empirically characterized. A direct experiment would compare three estimation strategies on the same training run: (1) the current epoch-based method, (2) an exponential moving average with various decay rates updated after each iteration, and (3) a ground-truth p_i oracle computed by periodically generating ~256 samples per prompt to estimate true success rates. The key metric would be the correlation between estimated and true p_i over the course of training, and the downstream impact on benchmark performance. This would quantify how much the 20–40% effective gradient ratio improvement (Figure 6) depends on estimation accuracy vs. the allocation optimization itself. A finding that online estimation significantly outperforms epoch-based estimation would justify the modest implementation complexity; a finding of no difference would validate the simplicity of the current approach.

Stress-testing the InfoGain(p_i) \approx p_i(1-p_i)^2 approximation against alternative value functions. The paper's value function is the intellectual engine of the allocation framework, but its InfoGain component is derived from a first-order Taylor expansion under idealized assumptions (softmax policy, unit advantage, small updates) and validated only in a synthetic 100-action setting (Figure 10). The allocation's sensitivity to this functional form is unknown. A systematic ablation would test Knapsack-GRPO with alternative InfoGain formulations: (a) constant InfoGain(p_i) = 1 (making value proportional to ProbNonZeroGradient alone, which would naively allocate maximum budget to the hardest prompts to maximize gradient probability), (b) InfoGain(p_i) = p_i(1-p_i) (the variance of the Bernoulli, symmetric around 0.5), (c) InfoGain(p_i) = -p_i \log p_i - (1-p_i) \log(1-p_i) (entropy, maximized at 0.5), and (d) a learned InfoGain function trained to predict actual per-step improvement from historical training data. The key finding would be whether the p(1-p)^2 form (with its peak at 1/3 and claimed asymmetry favoring harder prompts) is necessary for the observed gains, or whether any reasonable function that peaks at intermediate difficulty and decays at extremes would suffice. If the latter, the specific approximation is less important than the general principle; if the former, the theoretical derivation carries genuine practical weight.

Scaling behavior with model size: does the ~2× resource equivalence hold for 70B+ models? The paper's budget scaling experiment (Figure 9) demonstrates approximate 2× resource equivalence for Qwen2.5-Math-7B, but no experiments test larger models. A natural extension would train a 70B-class model (e.g., Llama-3-70B or Qwen-70B) on DAPO-Math-17K using both GRPO and Knapsack-GRPO at multiple total budgets, measuring whether the resource equivalence ratio changes with scale. The theoretical analysis predicts that harder-to-explore models (those with lower baseline p_i distributions) would benefit MORE from heterogeneous allocation, because the gap between N=8 uniform and the budgets needed for hard prompts would be larger. Conversely, stronger models that start with higher p_i on many prompts might benefit less, because fewer prompts fall into the "underexplored hard" category. The key measurement would be the \hat{p}_i distribution at initialization for models of different scales — if larger models have systematically higher \hat{p}_i, the knapsack benefit might shrink with scale, suggesting the approach is most valuable for modestly-capable models rather than frontier systems.

Combining knapsack exploration with tree-search or best-of-N generation strategies. The paper's exploration mechanism is simple on-policy random sampling — the model generates N_i independent autoregressive sequences per prompt. This leaves on the table the possibility of more sophisticated exploration strategies, such as Monte Carlo Tree Search (MCTS) guided by a process reward model, or best-of-N sampling with verifier-based selection. The knapsack framework could allocate a generation budget that is then spent on tree-search expansion rather than independent sampling, potentially producing higher-quality positive trajectories for the same compute cost. A concrete experiment would compare Knapsack-GRPO with three exploration backends: (a) independent sampling (current method), (b) beam search with a process reward model, where N_i controls the beam width, and (c) MCTS with rollouts, where N_i controls the number of tree expansions. The hypothesis is that tree-search exploration would increase the effective p_i for hard prompts (because search is more likely to find a correct solution than random sampling) while requiring more compute per trajectory, changing the optimal allocation surface. The key metric would be whether Knapsack + tree-search outperforms Knapsack + independent sampling at equal total FLOPs — if so, the allocation framework generalizes beyond its current exploration primitive.

Domain transfer: applying Knapsack RL to code generation and agentic tasks with non-binary rewards. All experiments are on math reasoning with binary verifiable rewards (Equation 2). The ProbNonZeroGradient formulation assumes binary outcomes; extending to continuous rewards (e.g., code execution success rate, BLEU scores, agent task completion percentages) requires redefining the "zero gradient" condition. For continuous rewards, GRPO's advantage is zero only when all N_i responses for a prompt receive IDENTICAL rewards — a much rarer event than in the binary case, potentially reducing the effective gradient ratio problem and thus the knapsack's benefit. A direct replication of Figure 2 and Figure 6 on a code generation RL dataset (e.g., using the Verl framework with execution-based rewards on APPS or CodeContests) would establish whether the zero-gradient problem is as severe in non-binary domains. If the effective gradient ratio is naturally higher (because continuous rewards rarely produce exact ties), the knapsack approach may provide smaller benefits, and its value would depend more on the InfoGain term's ability to identify improvable prompts than on the ProbNonZeroGradient term's ability to avoid wasted gradients.

Experience replay for prompts that remain extremely-hard despite large exploration budgets. The finding that approximately 3,000 prompts (out of 17,917) never produced a correct response even with Knapsack-GRPO's enhanced exploration (Section 5.2, Figure 8) identifies a hard failure mode: prompts that are fundamentally beyond the model's current capability. Budget reallocation cannot help these prompts because no finite exploration budget will find a correct trajectory. A potential solution is experience replay: store successful trajectories from OTHER prompts (including those that were eventually solved) and use them as positive examples for similar unsolved prompts. This would require a mechanism for identifying prompt similarity (e.g., embedding-based retrieval or topic modeling) and a training objective that encourages transfer (e.g., multi-task learning or in-context example conditioning). A concrete experiment would measure whether the 3,000 never-solved prompts under Knapsack-GRPO can be partially resolved by fine-tuning on (similar_prompt, correct_solution) pairs extracted from the training data, and whether this combined approach (knapsack allocation + replay) outperforms either alone. This would address the fundamental limitation identified in Limitation 2: that the knapsack framework amplifies existing capability but cannot create it from nothing.

Practical Applications and Downstream Use Cases

Cost-efficient RL training for mathematical reasoning models. The most direct application is to RL post-training pipelines that use GRPO (or compatible algorithms) on math reasoning datasets. The Verl framework used in this paper is widely adopted, and the knapsack modification requires changing only a few lines of budget allocation code (Listing 1) with no additional hyperparameters. A team training a math-specialized LLM on a dataset like DAPO-Math-17K, MetaMath, or NuminaMath can expect a ~2× reduction in required GPU hours to reach a given accuracy target (Figure 9), or equivalently, +2–4 point average benchmark improvements for the same compute budget (Table 2). For a typical training run that costs 1,400 A100 GPU hours (the paper's reported cost for Qwen2.5-Math-7B), this translates to approximately 1,000–2,000insavedcomputecostsatcurrentcloudpricing(assuming‘ 1,000–2,000 in saved compute costs at current cloud pricing (assuming `~1.50–$2.00` per A100 GPU hour), making the integration cost (1–2 seconds of CPU time per iteration, negligible engineering effort) essentially zero relative to the savings.

Training on heterogeneous datasets where prompt difficulty varies widely. The knapsack framework's benefit scales with the variance of p_i across the training set — it helps most when there are both very easy prompts (to economize on) and hard-but-feasible prompts (to invest in). This makes it particularly well-suited to datasets that aggregate problems from multiple sources with different difficulty levels, such as the DAPO-Math-17K dataset used in this paper, which draws from diverse math competition and benchmark sources. A practitioner curating a training dataset for RL post-training can actively design for knapsack compatibility by including a mix of easy, medium, and hard problems, knowing that the allocator will automatically redistribute budget toward the improvable middle. This contrasts with the standard advice to filter out "too easy" or "too hard" problems — the knapsack framework makes those problems useful as sources of saved budget or exploration targets, respectively.

Budget-constrained RL training on limited hardware. The budget scaling results (Figure 9) show that Knapsack-GRPO at N_total = 1024 (equivalent to N = 4 uniform) achieves comparable performance to GRPO at N_total = 2048 (N = 8). This means practitioners with limited GPU memory — who might be forced to use N = 4 or N = 2 to fit within their memory budget — can recover most of the performance of N = 8 uniform allocation through smarter distribution. This is particularly relevant for academic labs or individual researchers training on 1–4 GPUs, where memory constraints force small per-prompt budgets but the total compute across iterations is still substantial. The knapsack approach allows them to allocate those scarce budgets where they matter most, partially compensating for the lack of parallelism that larger labs enjoy.

Monitoring and diagnosing RL training runs. Even if a practitioner chooses not to adopt the knapsack allocator, the paper's diagnostic framework — tracking the effective gradient ratio, zero-gradient ratios from all-positive and all-negative rewards, and prompt status distributions (Figures 2, 6, 7, 8) — provides a valuable lens for understanding RL training dynamics. A team observing a declining effective gradient ratio in late training (as in Figure 2's 600+ iteration phase) now has a name for the problem and a hypothesized cause (increasing all-positive rewards from mastered prompts crowding out hard-prompt exploration). The transition matrix analysis (Figure 7) offers a way to track whether hard prompts are being converted to solvable ones or remaining stuck, enabling early detection of training plateaus. These diagnostics are independent of the knapsack solver and can be added to any GRPO training run with minimal instrumentation.

When to Prefer This Method

The paper positions Knapsack-GRPO directly against standard GRPO with uniform exploration budget allocation, and the empirical results establish clear preference conditions:

Prefer Knapsack-GRPO over standard GRPO when:

  • The training dataset has heterogeneous difficulty — a mix of prompts with widely varying success rates under the current policy. This is the condition that creates both easy prompts to economize on and hard prompts to invest in. Datasets like DAPO-Math-17K (aggregated from multiple sources) naturally exhibit this heterogeneity; a dataset of uniformly difficult competition problems might not.
  • The total exploration budget is constrained relative to the exploration demands of the hardest prompts. Knapsack-GRPO's advantage is largest at low total budgets (Figure 9: +5.7 points at N_total = 1024 vs. +2.3 at N_total = 2048) because reallocation matters more when the uniform budget is insufficient for hard prompts.
  • You are training from a base or instruction-tuned model (not a model already optimized near the performance ceiling). The Qwen3-4B-Base model showed the largest benchmark-level gains (+9.1 on AMC, Table 2), while the already-strong Qwen3-4B-Instruct showed regressions on some benchmarks, suggesting the method is most reliable when there is substantial headroom for improvement.
  • You are using GRPO or an algorithm with similar gradient structure (RLOO, per Appendix B). The ProbNonZeroGradient formulation is specific to algorithms where zero gradients arise from homogeneous rewards within a prompt's response group. For algorithms with different gradient conditions (e.g., ReMax, which requires only that a sampled trajectory differs from the greedy response), the knapsack formulation would need adaptation (Appendix B sketches this but does not validate it).

Consider standard GRPO or alternative approaches when:

  • The training dataset is uniformly easy or uniformly hard — if most prompts have p_i \approx 0 or p_i \approx 1, the knapsack has little room to reallocate (extreme prompts receive minimum budgets, leaving most of the budget unused or allocated via the fallback heuristic rather than the optimization).
  • You are training an already-strong instruction-tuned model near the top of its capability range on the target benchmark. The Qwen3-4B-Instruct results (regressions on AMC: -1.8, MINERVA: -3.6; Table 2) suggest the method can backfire when the model starts with high success rates, potentially because reallocating budget away from easy prompts causes forgetting without sufficient counterbalancing benefit on the remaining hard prompts.
  • Your primary goal is maintaining performance on already-mastered skills rather than improving on hard problems. The knapsack allocator explicitly deprioritizes prompts with p_i \approx 1.0 (allocating only N_low = 2), which may cause regression on prompts where mastery is fragile. If catastrophic forgetting is a larger concern than exploration efficiency, uniform allocation with a higher N provides more consistent monitoring of all prompts.
  • You are operating in a domain with non-binary or noisy rewards where the zero-gradient condition is rare or the success rate estimation is unreliable. The value function's dependence on accurate \hat{p}_i means that noisy reward signals would produce noisy allocations, potentially doing more harm than good. The paper provides no evidence about performance in such settings.