# G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 70 references that are in the map.
- First posted on arXiv 9 Feb 2026.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [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)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design](https://mlsanity.com/paper/2505.12285/) (2025)
- [Skywork-SWE: Unveiling Data Scaling Laws for Software Engineering in LLMs](https://mlsanity.com/paper/2506.19290/) (2025)
- [Skywork-Math: Data Scaling Laws for Mathematical Reasoning in Large Language Models -- The Story Goes On](https://mlsanity.com/paper/2407.08348/) (2024)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [HiFo-Prompt: Prompting with Hindsight and Foresight for LLM-based Automatic Heuristic Design](https://mlsanity.com/paper/2508.13333/) (2025)
- [SAT-LDM: Provably Generalizable Image Watermarking for Latent Diffusion Models with Self-Augmented Training](https://mlsanity.com/paper/2501.00463/) (2024)

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

- [AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design](https://mlsanity.com/paper/2605.08756/) (2026)
- [LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization](https://mlsanity.com/paper/2606.00718/) (2026)
- [SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems](https://mlsanity.com/paper/2607.23676/) (2026)
- [CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2605.06341/) (2026)
- [Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks](https://mlsanity.com/paper/2606.01975/) (2026)
- [PACE: Primitive-Aware Code Evolution for Automated Algorithm Design](https://mlsanity.com/paper/2608.07395/) (2026)
- [SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization](https://mlsanity.com/paper/2609.31179/) (2026)

## Abstract (arXiv)

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing approaches typically formulate AHD around constructive priority rules or parameterized local search guidance, thereby restricting the search space to fixed heuristic forms. Such designs offer limited capacity for structural exploration, making it difficult to escape deep local optima in complex Combinatorial Optimization Problems (COPs). In this work, we propose G-LNS, a generative evolutionary framework that extends LLM-based AHD to the automated design of Large Neighborhood Search (LNS) operators. Unlike prior methods that evolve heuristics in isolation, G-LNS leverages LLMs to co-evolve tightly coupled pairs of destroy and repair operators. A cooperative evaluation mechanism explicitly captures their interaction, enabling the discovery of complementary operator logic that jointly performs effective structural disruption and reconstruction. Extensive experiments on challenging COP benchmarks, such as Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP), demonstrate that G-LNS significantly outperforms LLM-based AHD methods as well as strong classical solvers. The discovered heuristics not only achieve near-optimal solutions with reduced computational budgets but also exhibit robust generalization across diverse and unseen instance distributions.