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

📄 arXiv: 2601.22896v1 📥 PDF

作者: Xinyi Ke, Kai Li, Junliang Xing, Yifan Zhang, Jian Cheng

分类: cs.AI

发布日期: 2026-01-30

💡 一句话要点

提出ASRO框架以解决LLM基础启发式发现中的过拟合问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自动启发式发现 博弈论 动态策略 组合优化 大型语言模型

📋 核心要点

  1. 现有的自动启发式发现方法主要依赖于静态评估，容易导致过拟合和泛化能力不足。
  2. 本文提出的ASRO框架通过博弈论视角实现求解器与实例生成器的共进化，动态调整策略。
  3. ASRO在多个组合优化领域中表现优异，相比静态训练基线显著提升了泛化能力和鲁棒性。

📝 摘要（中文）

大型语言模型（LLMs）在自动启发式发现（AHD）方面取得了快速进展，但现有方法主要受限于对固定实例分布的静态评估，导致潜在的过拟合和在分布变化下的泛化能力不足。本文提出了算法空间响应神谕（ASRO），一个将启发式发现重新构建为求解器与实例生成器之间的程序级共进化的博弈论框架。ASRO将其交互建模为一个双人零和博弈，维护双方不断增长的策略池，并通过基于LLM的最佳响应神谕对抗混合对手元策略，迭代扩展策略池，从而用自适应、自生成的课程替代静态评估。在多个组合优化领域中，ASRO在相同程序搜索机制下的静态训练AHD基线中表现出色，在多样化和超出分布的实例上实现了显著提高的泛化能力和鲁棒性。

🔬 方法详解

问题定义：本文旨在解决现有自动启发式发现方法在静态评估下的过拟合问题，导致在分布变化时的泛化能力不足。

核心思路：ASRO框架将启发式发现视为求解器与实例生成器之间的博弈，通过动态调整策略池来适应不同的实例分布，从而提高模型的泛化能力。

技术框架：ASRO的整体架构包括求解器和实例生成器两个主要模块，采用双人零和博弈的形式进行交互，策略池在每次迭代中不断扩展，利用LLM生成最佳响应。

关键创新：ASRO的核心创新在于将静态评估转变为自适应的课程学习，通过博弈论的方式实现求解器与实例生成器的动态共进化，显著提升了模型的适应性和鲁棒性。

关键设计：ASRO中采用的关键设计包括动态策略池的维护机制、基于LLM的最佳响应生成方法，以及对抗混合对手元策略的迭代扩展过程，这些设计共同促进了模型的自适应能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在多个组合优化领域的实验中，ASRO框架相比于静态训练的AHD基线表现出显著的性能提升，具体数据表明其在多样化和超出分布的实例上泛化能力提高了XX%，鲁棒性也得到了显著增强。

🎯 应用场景

该研究的潜在应用领域包括组合优化、自动化决策系统和智能算法设计等。通过提高启发式发现的泛化能力，ASRO框架能够在实际应用中更好地应对多样化和动态变化的环境，具有重要的实际价值和未来影响。

📄 摘要（原文）

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.