# Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 52 references that are in the map.
- First posted on arXiv 26 Nov 2021.

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

- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)

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

- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)
- [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023)
- [IsingFormer: Augmenting Parallel Tempering With Learned Proposals](https://mlsanity.com/paper/2509.23043/) (2025)
- [Generalized Probabilistic Approximate Optimization Algorithm](https://mlsanity.com/paper/2507.07420/) (2025)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Probabilistic Algorithms for Ising Machines from Optimization to Generative AI](https://mlsanity.com/paper/2610.03972/) (2026)

## Abstract (arXiv)

Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computational effort is generally required to unfreeze such variables and explore other unseen regions of the configuration space. Here, we introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy that can efficiently learn key instance-wise geometrical features of the cost function. That information is employed on-the-fly to construct spatially inhomogeneous thermal fluctuations for collectively unfreezing variables at various length scales, circumventing costly exploration versus exploitation trade-offs. We apply our algorithm to two of the most challenging combinatorial optimization problems: random k-satisfiability (k-SAT) near the computational phase transitions and Quadratic Assignment Problems (QAP). We observe significant speedup and robustness over both specialized deterministic solvers and generic stochastic solvers. In particular, for 90% of random 4-SAT instances we find solutions that are inaccessible for the best specialized deterministic algorithm known as Survey Propagation (SP) with an order of magnitude improvement in the quality of solutions for the hardest 10% instances. We also demonstrate two orders of magnitude improvement in time-to-solution over the state-of-the-art generic stochastic solver known as Adaptive Parallel Tempering (APT).