Robust Heuristic Algorithm Design with LLMs

Abstract — We posit that we can generate more robust and
performant heuristics if we augment approaches using LLMs
for heuristic design with tools that explain why heuristics
underperform and suggestions about how to fix them. We
find even simple ideas that (1) expose the LLM to instances
where the heuristic underperforms; (2) explain why they
occur; and (3) specialize design to regions in the input space,
can produce more robust algorithms compared to existing
techniques — the heuristics we produce have a ∼ 28× better
worst-case performance compared to FunSearch, improve
average performance, and maintain the runtime.