PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs

Large Language Models (LLMs) have enabled automated heuristic design (AHD) for combinatorial optimization problems (COPs), but existing frameworks' reliance on fixed evolutionary rules and static prompt templates often leads to myopic heuristic generation, redundant evaluations, and limited reasoning about how new heuristics should be derived. We propose a novel multi-agent reasoning framework, referred to as Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (PathWise), which formulates heuristic generation as a sequential decision process over an entailment graph serving as a compact, stateful memory of the search trajectory. This approach allows the system to carry forward past decisions and reuse or avoid derivation information across generations. A policy agent plans evolutionary actions, a world model agent generates heuristic rollouts conditioned on those actions, and critic agents provide routed reflections summarizing lessons from prior steps, shifting LLM-based AHD from trial-and-error evolution toward state-aware planning through reasoning. Experiments across diverse COPs show that PathWise converges faster to better heuristics, generalizes across different LLM backbones, and scales to larger problem sizes.

Many real-world challenges, such as planning delivery routes, packing trucks, and scheduling tasks, rely on practical decision-making procedures called heuristics. Designing good heuristics traditionally requires deep human expertise, so recent work explores using large language models (LLMs) to write them automatically. However, current LLM-based methods generate candidate heuristics somewhat blindly: they often produce many similar attempts, repeat past mistakes, and miss promising directions. PathWise takes a more deliberate approach. Multiple AI agents work together around a shared memory map that records every heuristic generated, why it was created, and how well it performed. One agent plans which prior heuristics to build on, another writes the new code, and two others critique the choices and suggest adjustments for the next step. This memory-driven design helps PathWise discover stronger heuristics faster, with less wasted computation. By shifting automated algorithm design from random trial-and-error toward planning with memory, PathWise makes LLM-driven optimization more efficient and dependable for real-world use.