Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery

Large language models (LLMs) have enabled rapid progress in automatic heuristic discovery (AHD), yet most existing methods are predominantly limited by static evaluation against fixed instance distributions, leading to potential overfitting and poor generalization under distributional shifts. We propose Algorithm Space Response Oracles (ASRO), a game-theoretic framework that reframes heuristic discovery as a program level co-evolution between solver and instance generator. ASRO models their interaction as a two-player zero-sum game, maintains growing strategy pools on both sides, and iteratively expands them via LLM-based best-response oracles against mixed opponent meta-strategies, thereby replacing static evaluation with an adaptive, self-generated curriculum. Across multiple combinatorial optimization domains, ASRO consistently outperforms static-training AHD baselines built on the same program search mechanisms, achieving substantially improved generalization and robustness on diverse and out-of-distribution instances.

Large language models can now help design new algorithms for difficult planning and optimization problems, such as routing vehicles or packing items efficiently. However, most existing approaches improve algorithms by testing them on a fixed set of examples. This often causes the resulting algorithms to perform poorly when faced with new or more complex situations. We propose a new framework called ASRO that models algorithm development as a competitive co-evolution process between two AI agents. One agent develops solving strategies, while the other generates increasingly challenging problem instances that expose weaknesses in current solutions. Instead of relying on fixed datasets, both agents continuously adapt to each other over time. ASRO is inspired by ideas from game theory and maintains a diverse set of strategies throughout training, enabling sustained improvement rather than early stagnation. We evaluate ASRO on several classic optimization problems, including online bin packing, the traveling salesman problem, and vehicle routing. Across all tasks, ASRO consistently achieves more robust and generalizable performance than existing large-language-model-based methods trained on fixed data. These results highlight this game-theoretic approach as an effective framework for AI-driven algorithm design.