# Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation

arXiv: https://arxiv.org/abs/2509.25849 · HTML: https://mlsanity.com/paper/2509.25849/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 30 Sep 2025.

## Builds on (most cited first, 30 of 32)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel](https://mlsanity.com/paper/2304.11277/) (2023)
- [Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs](https://mlsanity.com/paper/2506.14245/) (2025)
- [ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models](https://mlsanity.com/paper/2505.24864/) (2025)
- [ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models](https://mlsanity.com/paper/2310.10505/) (2023)
- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [Seed1.5-Thinking: Advancing Superb Reasoning Models with Reinforcement Learning](https://mlsanity.com/paper/2504.13914/) (2025)
- [Rho-1: Not All Tokens Are What You Need](https://mlsanity.com/paper/2404.07965/) (2024)
- [Self-Evolving Curriculum for LLM Reasoning](https://mlsanity.com/paper/2505.14970/) (2025)
- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [A Survey on Large Language Models for Mathematical Reasoning](https://mlsanity.com/paper/2506.08446/) (2025)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Optimizing Chain-of-Thought Reasoners via Gradient Variance Minimization in Rejection Sampling and RL](https://mlsanity.com/paper/2505.02391/) (2025)
- [Policy Filtration for RLHF to Mitigate Noise in Reward Models](https://mlsanity.com/paper/2409.06957/) (2024)

## Built on by (most cited first, 22 of 22)

- [Self-Hinting Language Models Enhance Reinforcement Learning](https://mlsanity.com/paper/2602.03143/) (2026)
- [XRPO: Pushing the limits of GRPO with Targeted Exploration and Exploitation](https://mlsanity.com/paper/2510.06672/) (2025)
- [Train Less, Learn More: Adaptive Efficient Rollout Optimization for Group-Based Reinforcement Learning](https://mlsanity.com/paper/2602.14338/) (2026)
- [CoBA-RL: Capability-Oriented Budget Allocation for Reinforcement Learning in LLMs](https://mlsanity.com/paper/2602.03048/) (2026)
- [Learn Hard Problems During RL with Reference Guided Fine-tuning](https://mlsanity.com/paper/2603.01223/) (2026)
- [Learning to Hint for Reinforcement Learning](https://mlsanity.com/paper/2604.00698/) (2026)
- [V0: A Generalist Value Model for Any Policy at State Zero](https://mlsanity.com/paper/2602.03584/) (2026)
- [Composition-RL: Compose Your Verifiable Prompts for Reinforcement Learning of Large Language Models](https://mlsanity.com/paper/2602.12036/) (2026)
- [IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL](https://mlsanity.com/paper/2603.12151/) (2026)
- [ERPO: Token-Level Entropy-Regulated Policy Optimization for Large Reasoning Models](https://mlsanity.com/paper/2603.28204/) (2026)
- [Teaching Language Models to Reason with Tools](https://mlsanity.com/paper/2510.20342/) (2025)
- [GOPO: Policy Optimization using Ranked Rewards](https://mlsanity.com/paper/2602.03876/) (2026)
- [Goldilocks RL: Tuning Task Difficulty to Escape Sparse Rewards for Reasoning](https://mlsanity.com/paper/2602.14868/) (2026)
- [Do Not Step Into the Same River Twice: Learning to Reason from Trial and Error](https://mlsanity.com/paper/2510.26109/) (2025)
- [Nonsense Helps: Prompt Space Perturbation Broadens Reasoning Exploration](https://mlsanity.com/paper/2605.05566/) (2026)
- [Selective Off-Policy Reference Tuning with Plan Guidance](https://mlsanity.com/paper/2605.11505/) (2026)
- [Manifold Bandits: Bayesian Curriculum Learning over the Latent Geometry of Large Language Models](https://mlsanity.com/paper/2606.19750/) (2026)
- [LIMBO: Lifelong Inference-Time Memory and Budget Optimization for LLM Agents](https://mlsanity.com/paper/2609.14138/) (2026)
- [Video-HopChain: Multi-Hop Questions and Confidence-Gated Exploration for Video Reasoning Models](https://mlsanity.com/paper/2609.25773/) (2026)
- [Frontier Learning: Training LLM Reasoners at the Edge of Capability](https://mlsanity.com/paper/2609.35426/) (2026)
- [Prompts Live on an Arc: Gaussian Curricula in Fisher--Rao Coordinates for Rollout-Efficient GRPO](https://mlsanity.com/paper/2609.38018/) (2026)
- [CERO: Where and When to Allocate Rollouts for RL Post-Training](https://mlsanity.com/paper/2610.09679/) (2026)

## Abstract (arXiv)

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.