Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World

arXiv:2610.36618v1 Announce Type: cross Abstract: Large language models (LLMs) enable algorithm discovery for combinatorial optimization problems (COPs) through iterative program generation and evaluation. A central challenge is how to organize search to discover better algorithms within a limited budget. Our key insight is that past search trajectories and their recorded outcomes form an experience world, which can be used to facilitate the COP solving through replay. We introduce Dream-COP, in which a policy agent learns executable policies through dreaming in this experience world to guide a discovery agent in generating and refining COP programs. Specifically, policy replay provides feedback on the quality of the programs revealed and the search steps used, to guide policy selection more effectively. Across five COPs, extsc{Dream} discovers better algorithms than fixed exploration in both heuristic component design and complete solver generation. Particularly, it matches the optimal values on KP and reduces the gap on OBPP from 2.112% to 1.199% while using 42.5% fewer search requests. Moreover, the learned exploration policies transfer effectively across different COPs with the assitance of the experience world.

Related

• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs
• The Invisible Lottery: How Subtle Cues Steer Algorithm Choice in LLM Code Generation
• Code-MUE: Measuring Code LLMs' Uncertainty through Execution-based Semantic Interaction Graphs
• Scaffold-Conditioned Preference Triplets for Controllable Molecular Optimization with Large Language Models

Source: arXiv cs.AI | 2026-10-28