Reproduce “A Generative Neural Annealer for Black-Box Combinatorial Optimization” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yuan-Hang Zhang, Massimiliano Di Ventra

A Generative Neural Annealer (GNA) is introduced as an end-to-end solver for black-box combinatorial optimization, employing a temperature-conditioned transformer to learn Boltzmann distributions over solutions. The method demonstrates superior sample efficiency and solution quality on challenging NP-hard problems, uniquely finding global optima for 3-SAT and 3-XORSAT within limited query budgets while implicitly learning problem structure.

Key insights

  • Conditioning a generative model on inverse temperature allows it to learn a continuous spectrum of Boltzmann distributions, transitioning from high-temperature exploration to low-temperature exploitation.
  • The transformer's attention mechanism enables GNA to implicitly learn the underlying structural interactions and connectivity of variables within combinatorial problems directly from black-box evaluations.
  • Framing black-box optimization through the lens of statistical mechanics, by learning Boltzmann distributions, provides a powerful and general framework for global optimization that integrates exploration and exploitation.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.