# Reheated Gradient-based Discrete Sampling for Combinatorial Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 51 references that are in the map.
- First posted on arXiv 6 Mar 2025.

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

- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning](https://mlsanity.com/paper/1902.03932/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Data-Dependence of Plateau Phenomenon in Learning with Neural Network --- Statistical Mechanical Analysis](https://mlsanity.com/paper/2001.03371/) (2020)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)
- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)

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

- [Sampling from Energy distributions with Target Concrete Score Identity](https://mlsanity.com/paper/2510.23106/) (2025)
- [Entropy-Guided Sampling of Flat Modes in Discrete Spaces](https://mlsanity.com/paper/2505.02296/) (2025)
- [Fine-Tuning Low-Bit Models with Gradient in Quantized Code Space](https://mlsanity.com/paper/2608.30908/) (2026)
- [On the Dataless Training of Neural Networks](https://mlsanity.com/paper/2510.25962/) (2025)
- [Solving Integer Linear Programming with Parallel Tempering](https://mlsanity.com/paper/2605.29366/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.