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

arXiv:2608.07544 · cs.NE, cs.AI · Submitted 2026-07-31 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design".

Jane: The paper was written by Oguzhan Gungordu, Siheng Xiong and Faramarz Fekri from Georgia Institute of Technology.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, folks. Today we're digging into a paper that's got a mouthful of a title: "MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design." Jane, I gotta say, just reading that title out loud made me want a cup of coffee.

Jane: Ha, I know what you mean, Tom. But let's break it down, because underneath all that jargon is a really clever idea. So, when we talk about "heuristics," we're talking about the rules of thumb that solve problems like the traveling salesman problem—you know, finding the shortest route through a bunch of cities. For a long time, humans designed these by hand. Now, we're getting large language models to write the code for these heuristics automatically.

Tom: Right, and that's the "LLM-based Automated Heuristic Design" part. But the twist here is the word "adversarial." It's not just asking the AI to write a good heuristic. It's setting up a fight. One part of the system is trying to create problem instances that are hard for the current heuristics, and the other part is trying to create heuristics that are good at those hard instances.

Jane: Exactly. And the "co-evolution" means they're both getting better at the same time, pushing each other. The paper calls the whole thing MOSAIC, which is a nice name because it's about building a bigger picture from lots of smaller, specialized pieces.

Lu: And that's the real insight here, Tom. The title hints at "specialist heuristics." Instead of trying to find one single, perfect algorithm that works for every possible problem instance—which, by the way, the No Free Lunch theorem says is impossible—MOSAIC builds a portfolio of different heuristics, each one an expert in a specific region of the "instance space."

Meng: So, from an engineering standpoint, you're not deploying one algorithm. You're deploying a toolbox, and you need a way to pick the right tool for the job. That's a totally different problem than just optimizing a single function.

Tom: Meng, you're hitting on the practical side already. But before we get into the engineering, let's just appreciate the conceptual leap. The authors are saying, "Let's stop trying to find the one ring to rule them all, and instead build a team of specialists."

Jane: And the "adversarial" part is what makes the specialists so good. You can't just say, "Here's a region, go be good at it." You have to find the regions where your current heuristics are weak, and that's exactly what the instance generator is doing.

Lalam: From my perspective, the title also signals a shift in how we use language models. We're not just using them as a static source of code. We're using them as active participants in a search process, where their ability to reason about abstract structures—like "what makes this route hard?"—is the key ingredient.

Tom: So, Lalam, you're saying the LLM isn't just the writer, it's also the strategist?

Lalam: Precisely, Tom. It's the strategist that generates the instances to expose weaknesses and the strategist that reads the feedback to write better code. The title captures that dual role perfectly.

Jane: And that dual role is what we're going to dig into next. We've got the title, but the real meat is in the summary of how this co-evolution actually works. Stick around.

Summary: Jane: So we've established that MOSAIC is about building a team of specialist heuristics. But how does it actually do that? The summary in the paper gives us the blueprint, and it's built on something called a Quality–Diversity archive.

Tom: A Quality–Diversity archive. Sounds like a fancy term for a filing cabinet.

Jane: That's actually a pretty good analogy, Tom. Imagine a grid. One axis might be "how clustered are the cities?" and the other axis might be "how spread out are the distances?" Each cell in this grid represents a different kind of problem instance. The archive's job is to keep the best heuristic it has found for each cell.

Tom: So it's a filing cabinet where each drawer is a different type of problem, and you keep your best tool in each drawer.

Jane: Exactly. But the clever part is how it fills those drawers. The paper describes an adversarial loop. First, it picks two heuristics from distant parts of the grid. Then, it uses an LLM to evolve new problem instances that are specifically designed to make one of those heuristics look great and the other one look terrible.

Meng: So it's not just generating random hard problems. It's generating problems that are *discriminating*. They're designed to separate the two heuristics, to find the exact boundary where one wins and the other loses.

Jane: Precisely, Meng. And then it uses a decision tree to figure out, in feature space, where exactly those winning regions are. That's the "where" that scalar feedback—like just saying "heuristic A is better than B"—completely misses.

Lu: And this is the key contribution, I think. The paper replaces that scalar feedback with what they call "contrastive multi-directional reflection." Instead of just saying "A is better," the LLM is asked to generate three insights: one about why A wins in its region, one about why B wins in its region, and one about how to combine them.

Tom: So it's not just "A wins." It's "A wins here because of this specific mechanism, and B wins there because of that specific mechanism."

Lu: Exactly. And those insights are stored in the archive cells. So the archive isn't just a collection of code. It's a collection of code, plus the instances that justify it, plus the natural language explanations of why it works. It's a persistent memory.

Lalam: That's what I find most exciting. The archive becomes a living document. It's not just a static database of solutions. It's a database of *knowledge* about the problem space. And that knowledge is what guides the next generation of heuristics.

Tom: So the LLM isn't just writing code in a vacuum. It's reading the insights that were generated by previous battles and using them to write better code for the next battle.

Jane: And that's how the "co-evolution" works. The instances get harder, the heuristics get more specialized, and the archive gets richer. It's a beautiful feedback loop.

Tom: I'm starting to see the big picture. But I'm curious about the specifics. How much better is this than what came before? The summary mentions some pretty impressive numbers.

Jane: It does. And we're going to get into those numbers in a minute. But first, let's talk about what the paper is actually improving upon. Because it's not just about being a little bit better. It's about fixing a fundamental flaw in how we've been doing this.

Improvements: Tom: So, Jane, we've talked about the "what." Let's talk about the "why." Why is this paper such a big deal? What's wrong with the old way of doing things?

Jane: The old way, Tom, is like training a single athlete to run every race. You give them a fixed training set, you measure their average time, and you try to make them a little bit faster. But the world isn't one race. It's a marathon, a sprint, a hurdles race, and a steeplechase all at once.

Lu: And the paper makes a very specific point about this. It says existing methods optimize for average performance on a small, fixed dataset. That's the "average" part. But the No Free Lunch theorem tells us that no single heuristic can be the best at everything. So by optimizing for the average, you're guaranteed to get a heuristic that's mediocre at everything.

Meng: And there's a second problem. The feedback is just a scalar. It's a number that says "this heuristic is five percent better than that one." That number doesn't tell you *why* it's better. It doesn't tell you in which region of the instance space it's better. So the LLM is trying to improve code with a blindfold on.

Jane: Exactly. And that's where MOSAIC's improvements come in. First, it replaces the single heuristic with a portfolio of specialists. Second, it replaces the scalar feedback with these rich, multi-directional insights that are spatially anchored to specific regions.

Tom: So instead of a blindfolded athlete, you've got a coach who can say, "You're great at hills, but you need to work on your sprinting. Here's a specific drill for that."

Jane: That's the idea. And the third improvement is the adversarial instance generation. The old methods just use a fixed training set. MOSAIC actively seeks out the hardest, most discriminating instances to expose the weaknesses of the current portfolio.

Lalam: And this is crucial. The instances aren't just hard. They're *discriminating*. They're designed to make different heuristics perform differently. This means the archive isn't just filling up with heuristics that are all good at the same thing. It's filling up with heuristics that are good at *different* things. That's what creates the diversity in the Quality–Diversity archive.

Meng: And that diversity is what makes the final portfolio so powerful. When you have a new, unseen problem instance, you don't have to hope your one heuristic is good enough. You can pick the specialist that's best suited for that instance's features.

Tom: So the improvements are threefold: specialists instead of a generalist, rich insights instead of a scalar score, and adversarial training instead of a fixed dataset. That's a pretty compelling package.

Jane: And the results in the paper back it up. But before we get to the numbers, I want to make sure we appreciate the elegance of the whole system. The archive is both the training ground and the final product. The instances that are evolved to be hard are the same instances that are stored to train the next generation. It's all one continuous loop.

Lu: And that loop is what makes it so efficient. The knowledge isn't discarded after each iteration. It's accumulated in the archive, in the form of specialists, instances, and insights. It's a persistent, growing memory.

Tom: Alright, I'm convinced this is a clever idea. But the proof is in the pudding. Let's look at the first page and see what kind of results they're actually getting.

First Page: Jane: Okay, Tom, we're finally at the first page of the paper. And the abstract is dense, but it lays out the whole story. Let's talk about what it promises.

Tom: The big claim is that this portfolio of specialists consistently outperforms state-of-the-art LLM-based AHD methods. And they tested it on three classic problems: the Traveling Salesman Problem, the Knapsack Problem, and the Capacitated Vehicle Routing Problem.

Meng: And it's not just on the training distribution. The paper mentions testing across different problem sizes and different instance structures. That's the real test of generalization. It's easy to be good at the problems you trained on. It's hard to be good at problems you've never seen.

Lu: The abstract also highlights the dual nature of the contribution. It's not just about generating better heuristics. It's also about generating better *instances*. The co-evolved instances are shown to have higher feature-space coverage and stronger heuristic discrimination than existing evolutionary instance-generation baselines.

Tom: So it's a two-for-one deal. You get a better toolbox, and you get a better set of test problems to validate your toolbox against.

Jane: And that's a really important point for the research community. If you're trying to benchmark new heuristics, you need a diverse and challenging set of instances. MOSAIC provides a way to generate those instances automatically, tailored to expose the differences between any set of algorithms you care about.

Lalam: The abstract also mentions the "persistent memory" aspect. The archive isn't just a collection of code. It's a collection of code, representative instances, and localized insights. This is a step towards a more holistic form of automated design, where the system doesn't just produce a solution, but also produces the reasoning behind it.

Tom: So it's not just a black box that spits out code. It's a system that can explain *why* a particular heuristic works in a particular region.

Lalam: Exactly. And that explanation is what allows the system to improve itself. It's a form of self-reflection that's grounded in the actual structure of the problem space.

Meng: From a practical standpoint, the numbers in the paper are pretty convincing. They show the portfolio's gap to the optimal solution is significantly lower than the baselines. And that's across different LLM backbones, which suggests the framework is robust to the underlying model.

Tom: So the first page is a promise. It's a promise that this adversarial co-evolution, this building of a team of specialists, is a better way to do automated heuristic design. And the rest of the paper is the evidence.

Jane: And that evidence is strong. We've seen the conceptual framework, the improvements over the old methods, and the promise of the results. Now, let's wrap this up and think about what it all means.

Conclusion: Tom: Well, folks, we've spent a good chunk of time on "MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design." And I think we can all agree it's a pretty big deal.

Jane: It really is. We started with the title and the idea of a team of specialists. Then we saw how the Quality–Diversity archive and the adversarial loop make that idea a reality. We talked about the improvements over the old way of doing things—replacing scalar feedback with rich insights, and fixed datasets with adversarial instance generation.

Lu: And the core insight, I think, is that the problem isn't just about finding a good algorithm. It's about understanding the problem space itself. MOSAIC uses the LLM to explore that space, to find the regions where algorithms differ, and to build a portfolio that covers all of those regions.

Meng: From an engineering perspective, the most exciting part is the practical impact. This isn't just a theoretical exercise. It's a framework that can be applied to any combinatorial optimization problem. You give it a problem description, and it builds you a toolbox of specialized solvers. That's incredibly powerful.

Lalam: And I would add that the framework's ability to generate discriminating instances is a major contribution in itself. It gives us a way to create better benchmarks, which will help the entire field of optimization research move forward.

Tom: So, to sum it up: MOSAIC isn't just a new algorithm. It's a new philosophy. It's saying, "Stop trying to find the one perfect solution. Instead, embrace the diversity of the problem space and build a team of experts to conquer it."

Jane: And that philosophy is backed up by some impressive results. Lower gaps to optimal, better generalization, and a richer understanding of the problem landscape.

Tom: It's been a pleasure discussing this one. A big thank you to the authors for their work. And to our listeners, thanks for tuning in.

Jane: We'll be back soon with another paper. Until then, keep exploring.

Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Georgia Institute of Technology

cs.NE, cs.AI

Submitted: 2026-07-31

Updated: 2026-08-11

Code: https://github.com/jakobbossek/tspgen

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 76/100

The gist: MOSAIC is a grid-based co-evolutionary framework for automated heuristic design (AHD) that adversarially co-evolves problem instances and specialist heuristics inside a Quality–Diversity (QD)

Terminology

Summary

MOSAIC is a grid-based co-evolutionary framework for automated heuristic design (AHD) that adversarially co-evolves problem instances and specialist heuristics inside a Quality–Diversity (QD) archive indexed by structural instance features. The paper states: "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."

The framework addresses two key limitations of existing LLM-based AHD methods: "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."

The QD archive is described as follows: 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. The archive is indexed by bounded structural instance features, with each cell storing a specialist heuristic, up to three representative instances, and localized natural-language insights.

The co-evolutionary loop operates as follows: "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 framework's objective is formalized as a minimax game: "We express this as a minimax game, max h k min X k sum k in C P(h k; X k) - lambda C/G, with lambda > 0. The negative coverage term rewards the instance adversary for expanding coverage; the outer maximization seeks specialists robust to those adversarial choices."

The main contributions are: "(1) We introduce the first grid-based AHD framework that co-evolves instances and heuristics under an instance-space view, coupling feature-space coverage with algorithmic discrimination in an adversarial objective. (2) We replace scalar feedback with contrastive multi-directional reflection, whose insights are anchored by a decision tree to the feature-space regions where each parent wins. (3) We use the QD archive as a persistent memory of region specialists, representative instances, and localized insights, accumulating cross-regional knowledge across iterations."

The methodology proceeds through six steps per iteration: (1) distant parent pair selection, (2) discriminative instance generation, (3) decision-tree analysis, (4) grid update with contrastive multi-directional reflection, (5) pair crossover, and (6) region-aware mutation. After the evolutionary budget is exhausted, greedy selection extracts a compact complementary test-time portfolio.

Experiments evaluate MOSAIC on the Traveling Salesman Problem (TSP), the Knapsack Problem (KP), and the Capacitated Vehicle Routing Problem (CVRP), comparing against LLM-based AHD baselines ReEvo, MCTS-AHD, PathWise, and EoH-S, with GPT-4o-mini and GPT-5-nano as LLM backbones. The results show: "MOSAIC attains the lowest gap in Table 1 at every selection level, size, and LLM backbone. The Oracle rows show that the archive is a stronger heuristic pool than any baseline's, with gaps up to 35% lower on TSP and 70% lower on KP than the best baseline's."

For instance generation, the framework's generator "is the only one winning both axes: it attains the highest feature-space coverage and the hardest, most discriminating instances, while baselines trade one for the other. It covers 33% more of the feature grid than QD-EA while producing instances 23% harder and 34% more discriminating."

The ablation study on TSP shows the default configuration attains the lowest mean optimality gap (AVG = 9.57%). Key findings include: removing mutation causes the largest degradation (60% worse AVG), removing the QD grid worsens AVG by 37%, and removing insights from operator prompts has a larger effect than removing the operators entirely (mutation w/o insights worsens AVG by 24%, crossover w/o insight by 28%).

The paper concludes: "We presented MOSAIC, a grid-based co-evolutionary framework that couples discriminative instance generation with specialist heuristic generation inside a QD archive indexed by instance features. Contrastive multi-directional reflection anchors insights to each heuristic's winning regions, and the archive accumulates specialists, instances, and insights across iterations. Experiments across COPs showed consistent gains over LLM-based AHD methods, while the co-evolved instances surpassed evolutionary instance-generation baselines in coverage and discrimination."

Improvements for AI systems

Based on the MOSAIC paper, here are the specific improvements I can implement in AI systems, along with what the improved system can do.

What I will change: Instead of training or evaluating an AI system on a fixed, static dataset, I will implement a co-evolutionary loop where a generator AI continuously creates new, challenging test instances, and the solver AI (the system being improved) must adapt to them.

Specific implementation:

  • Generator Role: A dedicated LLM (or a classical EA with LLM-designed operators) will be tasked with generating instances that maximize the performance gap between the current best solver and a weaker alternative. This is done by evolving instances that are hard for one heuristic and easy for another, using the cost-ratio margin m(h i, h j) = f(h i(x)) / f(h j(x)) as the fitness function.

  • Solver Role: The system being improved will be periodically retrained or fine-tuned on these newly generated, hard instances. This forces it to specialize and close the weaknesses that the generator just exposed.

  • Persistent Memory: I will store the generated instances in a Quality-Diversity (QD) archive, indexed by structural features (e.g., for TSP: fraction of distinct distances and n strong). This ensures the system is not just trained on the latest batch but on a diverse set of historical challenges, preventing catastrophic forgetting.

What the improved AI system can do:

  • Generalize beyond its training distribution. It will not just be an expert on the initial data but will have been adversarially tested and improved on a wide range of structural variations.

  • Exhibit a portfolio of strategies. Instead of a single monolithic model, the system will maintain a set of specialized sub-models (or heuristics), each an expert in a different region of the instance space. At test time, a selection mechanism (like a decision tree) will route each new instance to the most appropriate specialist.

  • Self-assess and improve. It will continuously identify its own weaknesses by generating its own final exams and then studying for them.

By integrating these three improvements, the resulting AI system will be:

  1. Robust and Generalizable: It will not overfit to a single dataset but will be continuously tested and improved against a diverse, evolving set of challenges.

  2. Explainable and Self-Aware: It will be able to articulate why it makes certain decisions and what its specific weaknesses are, in the form of structured insights.

  3. Modular and Scalable: It will be a portfolio of specialists rather than a single monolithic model, making it easier to update, debug, and scale to new problem domains.

  4. A Continuous Learner: It will have a built-in mechanism for lifelong learning, where the generation of new challenges and the acquisition of new skills are tightly coupled in an adversarial loop.

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.

Sources

Related papers