LLM Agents as Autonomous Solvers of NP-Hard Problems

NP-hard problems sit at the heart of modern computing — from comparing molecular structures and matching schemas to routing vehicles and scheduling workloads. For decades, we've oscillated between two unsatisfying poles: hand-crafted heuristics that demand deep expertise and don't transfer, and neural approximators that need expensive ground-truth supervision (often itself NP-hard to generate), operate as black boxes, and crumble the moment the data distribution shifts.

A third path has recently emerged. Systems like FunSearch and AlphaEvolve have shown that LLMs, placed inside an evolutionary loop, can write programs that solve hard problems rather than predict solutions directly — producing interpretable, transferable heuristics that in some cases surpass decades of human design. In this talk, I'll share two pieces of work, done in collaboration with the AlphaEvolve team, that push this paradigm further. The first asks whether the approach extends to problems where ground truth itself is NP-hard to obtain, and shows that a program-synthesis agent can match or beat state-of-the-art neural approximators while generalizing across domains — no labels required. The second confronts a question this paradigm raises but doesn't yet answer: which LLM should drive each step of the evolutionary search? Bigger and pricier turns out not to be reliably better. I'll show how an online bandit-based router can orchestrate a pool of frontier and open-weight models into an ensemble that matches — and sometimes beats — the strongest soloist, while cutting API costs by up to 65%.

Together, these results sharpen a broader pattern worth taking seriously: the most effective agentic systems for hard combinatorial problems aren't single monolithic models doing inference, but evolutionary societies of LLMs writing code, critiquing each other, and adaptively choosing who speaks next.