Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation

ByteDance Seed (with CUHK-Shenzhen and the Shenzhen Research Institute of Big Data; first author Ziniu Li, senior author Zhi-Quan Luo) attacks the degenerate edge of uniform rollout budgets in GRPO-style RL: easy tasks always succeed and hard tasks always fail, and both produce zero gradients. Knapsack RL reframes per-task exploration as a knapsack problem — each task an "item" with a value and a cost — and optimizes the allocation of a fixed total rollout budget across tasks instead of splitting it uniformly.

In the RL-scaling taxonomy this is the adaptive-allocation counterpart to IsoCompute's uniform compute-optimal rules (which cite it as the adaptive alternative) and to BroRL's uniform rollout-width scaling.