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

• URL: http://arxiv.org/abs/2608.07544v1
• Date: Fri, 31 Jul 2026 04:22:17 GMT
• Title: MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design
• Abstract summary: We propose a grid-based framework that adversarially co-evolves problem instances and specialist features inside a Quality-Diversity (QD) archive.<n>For each pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances.<n>A LLM then contrasts the two reflections to produce multi-directional insights that persist in those regions and guide crossover and mutation.
• Score: 16.59846708454225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search [2.8822232242646533]
  We propose a framework that integrates constrained worst-case instance search within a neighborhood of a training distribution.<n> RAISE consistently maintains strong performance across all tested and problem scales.
  arXiv  Detail & Related papers  (2026-06-30T15:19:27Z)
• The Art of Interrogation: Consistency Amplifies Factuality in Spatial Reasoning [65.67266333751569]
  Current Large Reasoning Models (LRMs) exhibit remarkable general capabilities but significantly underperform in spatial reasoning tasks.<n>We propose a self-supervised reinforcement learning framework that targets the internal reasoning process without requiring ground-truth annotations.<n>We show that this label-free consistency training approaches the accuracy of models trained with ground-truth supervision and achieves similar generalization across diverse tasks and data domains.
  arXiv  Detail & Related papers  (2026-06-10T10:50:06Z)
• Deliberate Evolution: Agentic Reasoning for Sample-Efficient Symbolic Regression with LLMs [52.89778838903305]
  Deliberate Evolution (DE) is an agentic framework that decouples symbolic generation from search control.<n>Experiments on LLM-SRBench show that DE consistently outperforms representative LLM-based SR baselines across diverse scientific domains.
  arXiv  Detail & Related papers  (2026-06-03T02:22:16Z)
• Self-Evolving Spatial Reasoning in Vision Language Models via Geometric Logic Consistency [53.28076739140119]
  We propose a framework that enforces logical consistency in Vision-Language Models (VLMs) through geometric and linguistic duality operations.<n>SAGE is model-agnostic, data-efficient compared to prior GRPO methods, and can be applied as a lightweight post-training stage to any existing VLM.<n> Experiments on video and spatial reasoning benchmarks demonstrate consistent improvements over strong baselines.
  arXiv  Detail & Related papers  (2026-05-18T10:05:21Z)
• Multi-Paradigm Collaborative Adversarial Attack Against Multi-Modal Large Language Models [67.45032003041399]
  We propose a novel Multi-Paradigm Collaborative Attack (MPCAttack) framework to boost the transferability of adversarial examples against MLLMs.<n>MPCO adaptively balances the importance of different paradigm representations and guides the global optimisation.<n>Our solution consistently outperforms state-of-the-art methods in both targeted and untargeted attacks on open-source and closed-source MLLMs.
  arXiv  Detail & Related papers  (2026-03-05T06:01:26Z)
• ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback [0.0]
  We propose ReVEL: Multi-Turn Reflective LLM-Heuristic Evolution via Structured Performance Feedback.<n>The core of ReVEL lies in two mechanisms: (i) performance-profile grouping and (ii) multi-turn feedback-driven reflection.<n>Our results highlight multi-turn reasoning with structured grouping as a principled paradigm for automated design.
  arXiv  Detail & Related papers  (2026-03-05T04:52:11Z)
• G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design [7.681872137995253]
  We propose a generative evolutionary framework that extends Large Neighborhood Search (LNS) operators.<n>G-LNS leverages Large Language Models (LLMs) to co-evolve tightly coupled pairs of destroy and repair operators.<n>Experiments show that G-LNS significantly outperforms LLM-based AHD methods as well as strong classical solvers.
  arXiv  Detail & Related papers  (2026-02-09T04:13:35Z)
• Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery [37.96481049421407]
  Large language models (LLMs) have enabled rapid progress in automatic discovery.<n>We propose a game-theoretic framework that reframes discovery as a program level co-evolution between solver and instance generator.
  arXiv  Detail & Related papers  (2026-01-30T12:14:52Z)
• PACEvolve: Enabling Long-Horizon Progress-Aware Consistent Evolution [64.15555230987222]
  PACEvolve is a framework designed to robustly govern the agent's context and search dynamics.<n>We demonstrate that PACEvolve provides a systematic path to consistent, long-horizon self-improvement.
  arXiv  Detail & Related papers  (2026-01-15T18:25:23Z)
• Mixture of Ranks with Degradation-Aware Routing for One-Step Real-World Image Super-Resolution [76.66229730098759]
  In real-world image super-resolution (Real-ISR), existing approaches mainly rely on fine-tuning pre-trained diffusion models.<n>We propose a Mixture-of-Ranks (MoR) architecture for single-step image super-resolution.<n>We introduce a fine-grained expert partitioning strategy that treats each rank in LoRA as an independent expert.
  arXiv  Detail & Related papers  (2025-11-20T04:11:44Z)
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design [124.54166764570972]
  Combinatorial optimization problems are traditionally tackled with handcrafted algorithms.<n>Recent progress has highlighted the potential of automatics design powered by large language models.<n>We propose the Experience-Evolution Reflective Co-Guided of Prompt and Heuristics (EvoPH) for automatic algorithm design.
  arXiv  Detail & Related papers  (2025-09-29T09:24:09Z)
• HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs [7.04316974339151]
  Heuristic Design is an active research area due to its utility in solving complex search and NP-hard optimization problems.<n>We introduce HSEvo, an adaptive LLM-EPS framework that maintains a balance between diversity and convergence with a harmony search.
  arXiv  Detail & Related papers  (2024-12-19T16:07:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.