Knapsack RL: Compute-Efficient Reinforcement Learning via Heterogeneous Rollout Allocation

Reinforcement learning (RL) fine-tuning of Large Language Models (LLMs) is compute-intensive because each prompt requires generating multiple responses, or rollouts. To make the best use of GPU resources, the key question is how to allocate rollout-generation jobs across prompts. Existing methods typically use uniform allocation, assigning every prompt the same rollout budget. This is inefficient and ineffective: easy prompts are oversampled after they are already solved, while hard prompts receive too little exploration. In policy optimization methods such as Group Relative Policy Optimization (GRPO), both cases often yield near-zero gradients and limited learning progress. We address this problem by formulating rollout allocation as a computeconstrained resource allocation task, where each prompt-budget choice has an expected learning value and rollout cost. Based on this view, we propose Knapsack RL, a practical framework that uses knapsack optimization to assign heterogeneous, task-specific rollout budgets. It directs exploration toward prompts that benefit most from additional sampling. Applied to GRPO, Knapsack RL increases the effective-gradient ratio by up to 40%, enables larger budgets for challenging prompts, and improves mathematical reasoning by 2–4 points on average, with peak gains of up to 9 points. Achieving similar performance with uniform allocation requires about 2× more compute, demonstrating a simple and practical path toward scaling RL fine-tuning for LLMs.