# Stabilized Best-of-K Training for Neural Combinatorial Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 5 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 4 of 4)

- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems](https://mlsanity.com/paper/2505.15201/) (2025)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [Leader Reward for POMO-Based Neural Combinatorial Optimization](https://mlsanity.com/paper/2405.13947/) (2024)

## Abstract (arXiv)

Leader Reward modifies POMO training to emphasize the best trajectory produced by repeated inference. We test a narrow extension: replace its binary leader/non-leader distinction with a stabilized rank signal indexed by a sampling budget K. With the POMO architecture, 3,050-epoch schedule, and TSP-100 test set held fixed, the Leader Reward reimplementation obtains 7.7662 under 100-start, 8-augmentation greedy decoding, matching the reported 7.766 at its displayed precision. Under independent sampling, the stabilized K=8 recipe lowers realized Best-of-8 cost in all three paired training seeds: 7.7944 versus 7.8136. This observation is estimation-only and decoder-specific: three seeds are below the six-seed testing floor, Leader Reward is better at sampled K=1, and it remains slightly better under its original augmented-greedy protocol. We make no unbiased-estimator, universal superiority, or state-of-the-art claim.