Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget
  Allocation
Authors: name: Ziniu Li, name: Congliang Chen, name: Tianyun Yang, name: Tian Ding, name: Ruoyu Sun, name: Ge Zhang, name: Wenhao Huang, name: Zhi-Quan Luo
Organization: ByteDance Seed

Large Language Models (LLMs) can self-improve through reinforcement learning,
where they generate trajectories to explore and discover better solutions.
However, this exploration process is computationally expensive, often forcing
current methods to assign limited exploration budgets to each task. This
uniform allocation creates problematic edge cases: easy tasks consistently
succeed while difficult tasks consistently fail, both producing zero gradients
during training updates for the widely used Group Relative Policy Optimization
(GRPO). We address this problem from the lens of exploration budget allocation.
Viewing each task's exploration as an "item" with a distinct "value" and
"cost", we establish a connection to the classical knapsack problem. This
formulation allows us to derive an optimal assignment rule that adaptively
distributes resources based on the model's current learning status. When
applied to GRPO, our method increases the effective ratio of non-zero policy
gradients by 20-40% during training. Acting as a computational "free lunch",
our approach could reallocate exploration budgets from tasks where learning is
saturated to those where it is most impactful. This enables significantly
larger budgets (e.g., 93 rollouts) for especially challenging problems, which
would be computationally prohibitive under a uniform allocation. These
improvements translate to meaningful gains on mathematical reasoning
benchmarks, with average improvements of 2-4 points and peak gains of 9 points
on specific tasks. Notably, achieving comparable performance with traditional
homogeneous allocation would require about 2x the computational resources.