Robusta

We use heuristics to solve computationally difficult problems where optimal solutions are too expensive to deploy, hard to manage, or otherwise inefficient. Our prior work, MetaOpt, shows many of the heuristics academics have developed and operators deploy can severely underperform under certain workloads. With MetaOpt, we enabled operators to find and mitigate such scenarios when possible.

In Robusta we take a different approach: we aim to design algorithms that are Robust by design. Our approach is inspired by FunSearch and AlphaEvolve that combine LLMs and genetic search to generate «better performing» algorithms. In each step of the genetic search, FunSearch and AlphaEvolve use the LLM to generate new heuristics, «evaluate» the heuristic (though simulations), and use the result in the evolutionary process. Robusta takes this idea one step further. Unlike FunSearch/AlphaEvolve that rely solely on simulation scores, Robusta uses analytical explanations of why and when a heuristic underperforms.

Robusta is a giant leap forward in automated algorithm design. It extends MetaOpt’s reach as a productivity booster and enables operators to design heuristics that are guaranteed to perform well in practice.

How it works

Step1: Find adversarial examples (inputs that cause the heuristic to underperform compared to the optimal) using MetaOpt or MetaEase.

Step 2: Explain why performance drops under adversarial samples using XPlain

Step 3: Feed distilled explanations to the LLM -> Generate suggestions on how to improve it

Step 4: Feed suggestions into the LLM -> Uses genetic search or reinforcement learning to improve the heuristic

We repeat the above process for each adversarial subspace we find for the base heuristic.

We built Robusta based on the following observations:

(1) To robust-ify algorithm design, we should evaluate the heuristic on examples where it is likely to underperform. We use our prior work on MetaOpt (which analyzes a mathematical model of a heuristic to find when it underperforms), MetaEase (which can analyze the heuristic’s code instead), and XPlain (which uses the output of MetaOpt/MetaEase to find adversarial subspaces where the heuristic underperforms and explains why) to produce such examples. We find even such a simple change can help improve the quality of the heuristics we generate.

(2) While adversarial samples help the LLM design algorithms that are more Robust they do introduce a problem: too many samples can cause the context for the LLM to blow up which in turn can impact the quality of the results we get. Instead, Robusta first uses XPlain to describe WHY the heuristic underperforms on those adversarial samples, and then feeds these explanations to the LLM and asks for a «suggestion» for how to improve the heuristic. It then uses these suggestions to evolve the heuristic. As we can see in our results above, this approach helps further robust-ify the heuristics we create.

(3) To simplify algorithm design, we believe it is better to design a separate algorithm for regions of the input space that share similar complexity. We use the adversarial subspaces from XPlain to design a separate algorithm for each subspace. This allows us to find algorithms that are more robust.

Operators can combine these ideas with any revolutionary process such as genetic search or reinforcement learning to design better heuristics.

So are we done?

Not yet, our initial results show the promise of the ideas within Robusta to help create algorithms that are robust by design. To truly ensure the end-to-end process produces a robust solution, wen eed to overcome a critical research problem:

We need to quantify the performance gap of the new heuristics the LLM creates vs the optimal solution.

We need to enable the LLMs to model the heuristics mathematically in order to do the above.

We need to scale explanation distillation from small to large instances.

We must analyze the final LLM-generated solution and quantify its performance gap compared to the optimal solution. If the gap is still large, we should restart the search with the current heuristic as the seed and the new adversarial samples.

This requires we find a way to enable LLMs to mathematically model the heuristics in MetaOpt, or scale the approach in MetaEase, and use it to analyze the heuristic’s code directly. In addition, as the problem sizes get larger, scale may become a challenge, we need to find ways to generate explanations from smaller instances of the problem and distill suggestions before we design robust heuristics for larger instances of the problem.

Our goal is to turn heuristic design from an art into a science – where LLMs and formal analysis jointly guarantee performance.