# Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Equivariant Flows: Exact Likelihood Generative Learning for Symmetric Densities](https://mlsanity.com/paper/2006.02425/) (2020)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Flow-based generative models for Markov chain Monte Carlo in lattice field theory](https://mlsanity.com/paper/1904.12072/) (2019)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Equivariant flow-based sampling for lattice gauge theory](https://mlsanity.com/paper/2003.06413/) (2020)
- [Solving Statistical Mechanics Using Variational Autoregressive Networks](https://mlsanity.com/paper/1809.10606/) (2018)
- [Variational Neural Annealing](https://mlsanity.com/paper/2101.10154/) (2021)
- [Learning Lattice Quantum Field Theories with Equivariant Continuous Flows](https://mlsanity.com/paper/2207.00283/) (2022)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Scaling Up Machine Learning For Quantum Field Theory with Equivariant Continuous Flows](https://mlsanity.com/paper/2110.02673/) (2021)
- [Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut](https://mlsanity.com/paper/2210.00623/) (2022)
- [Wavelet Conditional Renormalization Group](https://mlsanity.com/paper/2207.04941/) (2022)
- [Accelerating Markov Chain Monte Carlo sampling with diffusion models](https://mlsanity.com/paper/2309.01454/) (2023)
- [Generative diffusion model with inverse renormalization group flows](https://mlsanity.com/paper/2501.09064/) (2025)
- [Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs](https://mlsanity.com/paper/1904.02231/) (2019)
- [Performance of machine-learning-assisted Monte Carlo in sampling from simple statistical physics models](https://mlsanity.com/paper/2505.22598/) (2025)
- [Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning](https://mlsanity.com/paper/2502.05537/) (2025)
- [Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem](https://mlsanity.com/paper/1906.10036/) (2019)
- [Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture](https://mlsanity.com/paper/2302.10848/) (2023)
- [Hierarchical autoregressive neural networks in three-dimensional statistical system](https://mlsanity.com/paper/2503.08610/) (2025)
- [IsingFormer: Augmenting Parallel Tempering With Learned Proposals](https://mlsanity.com/paper/2509.23043/) (2025)
- [BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints](https://mlsanity.com/paper/2009.06240/) (2020)
- [How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs](https://mlsanity.com/paper/2102.09510/) (2021)

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

- [Scalable Physics-Inspired Transformers for Spin Glasses](https://mlsanity.com/paper/2606.22984/) (2026)
- [The critical slowing down in training diffusion models](https://mlsanity.com/paper/2605.12597/) (2026)
- [Leveraging generative models to assist Monte Carlo sampling](https://mlsanity.com/paper/2608.07648/) (2026)
- [Discrete Diffusion Models via Evolving Variational Autoregressive Networks](https://mlsanity.com/paper/2609.27306/) (2026)
- [Probabilistic Algorithms for Ising Machines from Optimization to Generative AI](https://mlsanity.com/paper/2610.03972/) (2026)

## Abstract (arXiv)

Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning--assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization (QUBO) problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide clear and robust evidence that a machine learning--assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.