# Large Neighborhood Search meets Iterative Neural Constraint Heuristics

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 41 references that are in the map.
- First posted on arXiv 21 Mar 2026.

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

- [MaskGIT: Masked Generative Image Transformer](https://mlsanity.com/paper/2202.04200/) (2022)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Remasking Discrete Diffusion Models with Inference-Time Scaling](https://mlsanity.com/paper/2503.00307/) (2025)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning Iterative Reasoning through Energy Diffusion](https://mlsanity.com/paper/2406.11179/) (2024)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer](https://mlsanity.com/paper/2307.04895/) (2023)
- [Constrained Discrete Diffusion](https://mlsanity.com/paper/2503.09790/) (2025)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Learning Large Neighborhood Search for Vehicle Routing in Airport Ground Handling](https://mlsanity.com/paper/2302.13797/) (2023)
- [Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction](https://mlsanity.com/paper/2502.15794/) (2025)
- [Large Neighborhood Search based on Neural Construction Heuristics](https://mlsanity.com/paper/2205.00772/) (2022)
- [SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs](https://mlsanity.com/paper/2508.16171/) (2025)

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

- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)

## Abstract (arXiv)

Neural networks are being increasingly used as heuristics for constraint satisfaction. These neural methods are often recurrent, learning to iteratively refine candidate assignments. In this work, we make explicit the connection between such iterative neural heuristics and Large Neighborhood Search (LNS), and adapt an existing neural constraint satisfaction method-ConsFormer-into an LNS procedure. We decompose the resulting neural LNS into two standard components: the destroy and repair operators. On the destroy side, we instantiate several classical heuristics and introduce novel prediction-guided operators that exploit the model's internal scores to select neighborhoods. On the repair side, we utilize ConsFormer as a neural repair operator and compare the original sampling-based decoder to a greedy decoder that selects the most likely assignments. Through an empirical study on Sudoku, Graph Coloring, and MaxCut, we find that adapting the neural heuristic to an LNS procedure yields substantial gains over its vanilla settings and improves its competitiveness with classical and neural baselines. We further observe consistent design patterns across tasks: stochastic destroy operators outperform greedy ones, while greedy repair is more effective than sampling-based repair for finding a single high-quality feasible assignment. These findings highlight LNS as a useful lens and design framework for structuring and improving iterative neural approaches.