# MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 84 references that are in the map.
- First posted on arXiv 31 Jul 2026.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap](https://mlsanity.com/paper/2401.10034/) (2024)
- [LLMatic: Neural Architecture Search via Large Language Models and Quality Diversity Optimization](https://mlsanity.com/paper/2306.01102/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Harnessing the Power of Large Language Models for Natural Language to First-Order Logic Translation](https://mlsanity.com/paper/2305.15541/) (2023)
- [Large Language Models As Evolution Strategies](https://mlsanity.com/paper/2402.18381/) (2024)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [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)
- [The Importance of Directional Feedback for LLM-based Optimizers](https://mlsanity.com/paper/2405.16434/) (2024)
- [Quality Diversity for Multi-task Optimization](https://mlsanity.com/paper/2003.04407/) (2020)
- [Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Model](https://mlsanity.com/paper/2410.03136/) (2024)
- [Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation](https://mlsanity.com/paper/2311.13184/) (2023)
- [HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges](https://mlsanity.com/paper/2506.15196/) (2025)
- [Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization](https://mlsanity.com/paper/2502.11422/) (2025)
- [LLM-Driven Instance-Specific Heuristic Generation and Selection](https://mlsanity.com/paper/2506.00490/) (2025)
- [Code Evolution Graphs: Understanding Large Language Model Driven Design of Algorithms](https://mlsanity.com/paper/2503.16668/) (2025)
- [Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing](https://mlsanity.com/paper/2501.11411/) (2025)
- [Fitness Landscape of Large Language Model-Assisted Automated Algorithm Search](https://mlsanity.com/paper/2504.19636/) (2025)
- [PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs](https://mlsanity.com/paper/2601.20539/) (2026)

## Abstract (arXiv)

Automated heuristic design (AHD) with large language models (LLMs) has produced strong heuristics for combinatorial optimization problems (COPs). Yet existing frameworks optimize for average performance on a small fixed dataset and steer the search with "verbal gradients" distilled from scalar better/worse feedback. No single heuristic dominates across instance distributions, and scalar feedback tells the LLM whether a heuristic improved, but not where in the instance space or why. We propose MOSAIC, a grid-based framework that adversarially co-evolves problem instances and specialist heuristics inside a Quality-Diversity (QD) archive indexed by structural instance features. Instances evolve to expose weaknesses of the current heuristics, and heuristics evolve to eliminate them by specializing to the newly exposed regions. Each archive cell keeps a specialist heuristic, representative instances, and insights explaining what works in its region, forming a persistent memory that accumulates over the evolutionary search. For each heuristic pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances, and a decision tree identifies the feature-space regions where each heuristic wins. A reflection LLM then contrasts the two heuristics to produce multi-directional insights that persist in those regions and guide crossover and mutation. The archive is simultaneously a co-evolved benchmark of discriminative instances and a pool of region specialist heuristics, from which greedy selection extracts a compact complementary portfolio. Across COPs, test sizes, and LLM backbones, the portfolio consistently outperforms state-of-the-art LLM-based AHD methods, and the co-evolved instances attain higher feature-space coverage and stronger heuristic discrimination than evolutionary instance-generation baselines.