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

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.