# The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 48 references that are in the map.
- First posted on arXiv 27 Oct 2025.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Gemma 3 Technical Report](https://mlsanity.com/paper/2503.19786/) (2025)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [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)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [The Surprising Effectiveness of Negative Reinforcement in LLM Reasoning](https://mlsanity.com/paper/2506.01347/) (2025)
- [Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models](https://mlsanity.com/paper/2508.10751/) (2025)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling](https://mlsanity.com/paper/2406.00832/) (2024)
- [Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models](https://mlsanity.com/paper/2412.15287/) (2024)
- [Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems](https://mlsanity.com/paper/2505.15201/) (2025)

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

- [Vector Policy Optimization: Training for Diversity Improves Test-Time Search](https://mlsanity.com/paper/2605.22817/) (2026)
- [Frontis-MA1: Training an AI4AI Model towards Recursive Self-Improvement in Machine Learning Engineering](https://mlsanity.com/paper/2607.28568/) (2026)
- [Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying](https://mlsanity.com/paper/2606.00151/) (2026)
- [Regret Analysis of Retry-Based Bandits](https://mlsanity.com/paper/2605.20854/) (2026)
- [HTAM: Hierarchical Transition-Attended Memory for Operator Optimization](https://mlsanity.com/paper/2605.29734/) (2026)
- [On Advantage Estimates for Max@K Policy Gradients](https://mlsanity.com/paper/2606.06080/) (2026)
- [OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation](https://mlsanity.com/paper/2606.06096/) (2026)
- [Multi-Axis Max@K Reinforcement Learning for Representative Diversity in Text-to-Image Generation](https://mlsanity.com/paper/2607.14962/) (2026)
- [Inference-Aware Meta-Alignment of LLMs via Non-Linear GRPO](https://mlsanity.com/paper/2602.01603/) (2026)
- [Boosting LLM Reasoning via Human-Inspired Reward Shaping](https://mlsanity.com/paper/2602.04265/) (2026)
- [What should post-training optimize? A test-time scaling law perspective](https://mlsanity.com/paper/2605.10716/) (2026)
- [Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-K Objective](https://mlsanity.com/paper/2607.11146/) (2026)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)
- [Re3Cap: Retrieval-Guided Refinement for Image Captioning Enhancement via Reinforcement Learning](https://mlsanity.com/paper/2608.21305/) (2026)
- [The Statistical Benefits of Multiple Responses for Learning from Demonstrations](https://mlsanity.com/paper/2609.33291/) (2026)
- [SERA: Scale-Equalized Rollout Allocation for Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2609.36552/) (2026)

## Abstract (arXiv)

The application of Reinforcement Learning with Verifiable Rewards (RLVR) to mathematical and coding domains has demonstrated significant improvements in the reasoning and problem-solving abilities of Large Language Models. Despite its success in single generation problem solving, the reinforcement learning fine-tuning process may harm the model's exploration ability, as reflected in decreased diversity of generations and a resulting degradation of performance during Best-of-N sampling for large N values. In this work, we focus on optimizing the max@k metric, a continuous generalization of pass@k. We derive an unbiased on-policy gradient estimate for direct optimization of this metric. Furthermore, we extend our derivations to the off-policy updates, a common element in modern RLVR algorithms, that allows better sample efficiency. Empirically, we show that our objective effectively optimizes max@k metric in off-policy scenarios, aligning the model with the Best-of-N inference strategy.