# LLM-Driven Instance-Specific Heuristic Generation and Selection

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2025.

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

- [Policy and World Modeling Co-Training for Language Agents](https://mlsanity.com/paper/2606.02388/) (2026)
- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design](https://mlsanity.com/paper/2605.08756/) (2026)
- [EvoSpeak: Large Language Models for Interpretable Genetic Programming-Evolved Heuristics](https://mlsanity.com/paper/2510.02686/) (2025)
- [Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search](https://mlsanity.com/paper/2601.19622/) (2026)
- [Neural QAOA2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization](https://mlsanity.com/paper/2605.13072/) (2026)
- [SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems](https://mlsanity.com/paper/2607.23676/) (2026)
- [Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search](https://mlsanity.com/paper/2608.03129/) (2026)
- [Constraint-aware Path Planning from Natural Language Instructions Using Large Language Models](https://mlsanity.com/paper/2603.19257/) (2026)
- [MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design](https://mlsanity.com/paper/2606.14202/) (2026)
- [Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs](https://mlsanity.com/paper/2608.06808/) (2026)
- [MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design](https://mlsanity.com/paper/2608.07544/) (2026)
- [From Hand-Crafted to LLM-Based Variation Operators in Metaheuristics: A Tutorial](https://mlsanity.com/paper/2609.31649/) (2026)
- [Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs](https://mlsanity.com/paper/2610.03316/) (2026)

## Abstract (arXiv)

Combinatorial optimization problems are widely encountered in real-world applications. A critical research challenge lies in designing high-quality heuristic algorithms that efficiently approximate optimal solutions within a reasonable time. In recent years, many works have explored integrating Large Language Models (LLMs) with Evolutionary Algorithms to automate heuristic algorithm design through prompt engineering. However, these approaches generally adopt a problem-specific paradigm, applying a single algorithm across all problem instances, failing to account for the heterogeneity across instances. In this paper, we propose InstSpecHH, a novel framework that introduces the concept of instance-specific heuristic generation. InstSpecHH partitions the overall problem class into sub-classes based on instance features and performs differentiated, automated heuristic design for each problem subclass. By tailoring heuristics to the unique features of different sub-classes, InstSpecHH achieves better performance at the problem class level while avoiding redundant heuristic generation for similar instances, thus reducing computational overhead. This approach effectively balances the trade-off between the cost of automatic heuristic design and the quality of the obtained solutions. To evaluate the performance of InstSpecHH, we conduct comprehensive experiments on 4,500 subclasses of the Online Bin Packing Problem (OBPP) and 365 subclasses of the Capacitated Vehicle Routing Problem (CVRP). Experimental results show that InstSpecHH demonstrates strong intra-subclass and inter-subclass generalization capabilities. Compared to previous problem-specific methods, InstSpecHH reduces the average optimality gap by 6.06% for OBPP and 0.66% for CVRP. These results highlight the potential of instance-aware automatic heuristic design to further enhance solution quality.