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

AI summary

Overview

• Research area: Automated heuristic design (AHD) for combinatorial optimization problems (COPs), combining large language models (LLMs), multi-agent reasoning, and graph-based search.
• Technical level: Advanced — the paper builds on Markov Decision Process (MDP) formalism, entailment graphs, and multi-agent LLM orchestration for program synthesis.
• Scope: This paper introduces PathWise, a multi-agent LLM framework that reframes heuristic discovery as state-aware sequential planning over an entailment graph rather than fixed evolutionary or tree-based search, and evaluates it on six combinatorial optimization benchmarks across three search frameworks.

What This Paper Is About

Existing LLM-based methods for automatically designing heuristics for combinatorial optimization rely on fixed evolutionary rules, static prompt templates, and population- or tree-based search that treats each heuristic generation as an isolated step. This leads to myopic generation, redundant evaluations, and rediscovery of similar heuristics, because the systems lack a memory of how heuristics were derived or why edits succeeded or failed. PathWise addresses this by formulating heuristic generation as a sequential decision process over an entailment graph — a compact, stateful memory of the search trajectory — and by coordinating a policy agent, a world model agent, and two critic agents to plan, execute, and reflect on evolutionary actions.

Key Contributions

1. A hybrid graph-based and population-based formulation of heuristic evolution. An entailment graph encodes each heuristic's derivation rationale, parent metadata, algorithmic description, and performance history, serving as the shared state through which the policy and world model interact. Unlike population methods that discard intermediate results, derivation history is retained; unlike tree-based methods that keep all candidates, the population mechanism restricts each outer iteration's exploration to a compact set of root nodes.

2. A coordinated multi-agent LLM framework. A policy agent generates high-level evolutionary actions (parent selection plus a natural-language derivation rationale), a world model agent executes those actions through low-level heuristic code generation and updates the entailment graph, and two critic agents analyze graph structure and produce routed reflections that condition the policy and world model at the next step — enabling self-evolving, state-aware generation without updating any LLM parameters.

3. Prompt-level diversity mechanisms. Diversity-aware prompt perturbation, governed by a time-varying exploration rate that decays linearly from 0.5 to 0.25 over the evaluation budget, plus state shuffling to reduce positional bias in parent selection, broaden exploration over the entailment graph.

4. Extensive empirical evaluation across diverse COPs. PathWise is tested within step-by-step constructive, Ant Colony Optimization (ACO), and Guided Local Search (GLS) frameworks on TSP, KP, CVRP, MKP, OP, and BPP, demonstrating faster convergence, stronger heuristics with fewer evaluations, generalization across LLM backbones, and improved scaling to larger problem sizes.

Main Findings

• Fewer evaluations, better results. Figure 1 shows that on TSP and CVRP with GPT-4o-mini, PathWise is run with a limit of n_e = 500 evaluations while all baselines use n_e = 1000, yet it achieves stronger best-so-far performance with lower variance and faster convergence.

• Best overall on step-by-step construction (TSP and KP). In Table 1, PathWise outperforms the manually designed Greedy Construct heuristic and all LLM-based AHD baselines (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) on every test set. With GPT-4o-mini on TSP N=50, PathWise reaches objective 6.245 (9.81% gap) versus MCTS-AHD's 6.358 (11.80%) and HSEvo's 6.429 (13.05%). With GPT-5-nano (medium) on TSP N=200, PathWise reaches 12.009 (12.14% gap) versus MCTS-AHD's 12.148 (13.44%).

• Systematic gains as model capability increases. Performance improves when moving from GPT-4o-mini to GPT-5-nano, and further with higher reasoning levels. On TSP with GPT-5-nano (medium), PathWise attains objective 6.165 (8.41% gap) at N=50 and 12.009 (12.14% gap) at N=200.

• Mean relative gap improvement (MRGI) over LLM-based AHD baselines. On TSP, PathWise achieves an overall average improvement of 20.38% across test sets and LLM backbones, including 31.82% for GPT-5-nano (low). On KP, it achieves 49.89% (GPT-4o-mini), 20.26% (GPT-5-nano, low), and 65.20% (GPT-5-nano, medium).

• Scalability improves with problem size. Averaging MRGI per test set across LLM backbones, the improvement grows from 31.67% on the in-domain test set (N=100, W=25) to 81.34% on the largest out-of-domain test set (N=500, W=25).

• Competitive against a trained neural solver. PathWise achieves better performance on TSP (N=200) and KP test sets than POMO, a Neural Combinatorial Optimization method that requires task-specific training.

• Strong results in the ACO framework. In Table 2, PathWise attains near-zero gaps on several tasks — for example, with GPT-5-nano (medium) it reaches 0.00% gap on MKP (N=100, m=5, objective 22.050) and 0.00% gap on MKP (N=300, m=5, objective 58.159), versus DeepACO's 1.82% and 3.28% respectively. With GPT-4o-mini it reaches 0.00% gap on OP (N=200, objective 54.119).

• Gaps remain in some ACO settings. In the ACO framework, DeepACO holds the 0.00% reference gaps on TSP and CVRP test sets, and PathWise's CVRP gaps under GPT-4o-mini (5.53% at N=50, C=50; 10.30% at N=100, C=50) are larger than its gaps on other tasks.

• Not reported in the provided content. Results for the GLS framework, online BPP results, cost analysis, and heuristic output examples are stated to be in Appendix E, Appendix H, and Appendix G, respectively, and these appendices are not included in the supplied text. Ablation studies isolating individual components (policy, world model, critics, diversity mechanisms) are likewise not reported in the provided content.

Methodology in Plain English

PathWise treats heuristic design as a planning problem instead of trial-and-error evolution, and organizes search on two timescales.

Outer loop (populations). The system keeps a population of root heuristics of size N_p = 6. The first population is generated by prompting an LLM with an initialization prompt. After each round of inner search, the next population is formed by a leaf-first selection rule: take the best leaf nodes (nodes with no outgoing entailment edges) of the resulting graph, and if there are fewer leaves than N_p, fill the remainder with the best non-leaf nodes.

Inner loop (entailment graph). Starting from the current population as root nodes, the system repeatedly adds a new node derived from a selected parent set, building up a graph. Each node stores the heuristic code, the natural-language rationale used to derive it, an algorithmic description, its performance on the instance distribution, and compact parent metadata (the parents' descriptions and performance values, but not their full code — this keeps prompts small). Each directed edge records which parents entailed the child and under what rationale. After each entailment step, the newly created node is added, the parent nodes actually used are pruned away, and the global best node is retained — balancing exploration, exploitation, and search complexity.

The agent team. At each inner step:

• The policy agent observes the current graph state and produces N_a = 2 candidate actions. Each action is a pair: a selected parent set plus a natural-language directive describing how those heuristics should be modified or combined. Because the directive is free text rather than a fixed operator, the policy can invent new operator types and adapt strategy as search evolves.
• The world model agent takes each action, along with the selected parents' code and descriptions and its own routed reflection, and generates N_w = 2 candidate heuristic rollouts (code plus description). All rollouts are evaluated, and the best one is inserted into the graph as the entailed node. Only one node is added per inner step.
• The policy critic averages rollout performance for each action and receives a compact bundle of rollout descriptors, then writes a reflection about which derivation rationales and parent choices worked, which conditions the policy at the next step.
• The world model critic contrasts the best-performing rollout with the worst-performing one and writes a reflection on code-synthesis quality, which conditions the world model at the next step. The authors describe these as verbal gradients.

Diversity handling. If the policy keeps picking the same parents with similar directives and the world model produces similar code, the critics see no contrast and cannot say anything useful. To prevent this, the framework injects randomized exploratory phrases into the agents' prompts with a probability that decays linearly from 0.5 to 0.25 as evaluations accumulate — encouraging broad exploration early and focused refinement later. It also shuffles the order of nodes before prompting the policy agent and policy critic, so parent selection is driven by semantic fit rather than position in the context window.

Key design choice: no LLM parameters are updated. PathWise is training-free; all adaptation happens through natural-language reflections and graph state. The inner loop runs until a maximum of I_max = 3 entailment steps is reached or the frontier collapses to a single node.

Experimental setup: PathWise is tested with N_a = 2, N_w = 2, N_p = 6, I_max = 3, sampling temperature 1.0, using GPT-4o-mini (non-reasoning) and GPT-5-nano at low and medium reasoning levels. LLM-based AHD methods get n_e = 500 heuristic evaluations per task and a 60-second execution limit per heuristic on the training dataset, with results averaged over 3 runs. Task-level optimal baselines are LKH-3 for TSP and OR-Tools for KP. Code is publicly available at https://github.com/oguzhangungordu/PathWise.

Why This Matters

Research impact. The paper argues that the bottleneck in LLM-based AHD is not raw generation quality but the structure of search — fixed operators, stateless sampling, and performance-only selection criteria such as UCT. By recasting heuristic discovery as a sequential MDP with an explicit, semantic memory of derivations, PathWise offers a template for state-aware, reflection-driven program search that could transfer to domains beyond COPs where LLMs generate and refine code. It also demonstrates that a training-free, multi-agent design can compete with and beat both task-specifically trained neural solvers (POMO) and established LLM-based AHD methods on several benchmarks.

Real-world applications:

• Routing and logistics: TSP, CVRP, and OP heuristics directly support delivery routing, fleet dispatch, and field-service scheduling.
• Packing and resource allocation: KP, MKP, and offline/online BPP map to container loading, warehouse bin packing, cargo consolidation, and cloud resource assignment.
• Scheduling and design automation: the paper frames COPs as central to scheduling and design automation tasks where hand-crafted heuristics are costly to produce.
• Solver-augmented workflows: the framework designs heuristics inside existing solver frameworks (constructive, ACO, GLS), so discovered components can be dropped into production solvers rather than replacing them.

Industry relevance. Because PathWise is training-free and generalizes across LLM backbones, organizations can use it with whichever frontier model they already have access to, without collecting task-specific training data or fine-tuning. The paper's emphasis on achieving better heuristics with fewer LLM evaluations (500 versus 1000 in Figure 1) speaks directly to inference cost, a major practical constraint in LLM-driven optimization pipelines.

Future Directions

• Replacing reflections with gradient-based learning. PathWise is explicitly training-free: the policy and world model are steered only by natural-language critic reflections. An open question is whether the entailment graph's recorded actions, rationales, and rewards could instead supervise parameter updates or learned value models.

• Extending beyond the three studied search frameworks. The paper evaluates constructive, ACO, and GLS frameworks. Whether the entailment-graph formulation transfers to other solver families (for example, local search variants beyond GLS or other metaheuristics) is not addressed in the available content.

• Improving the weaker ACO settings. Gaps are largest on CVRP in the ACO framework (for example, 10.30% at N=100, C=50 with GPT-4o-mini), suggesting room for the derivation-rationale mechanism to better capture routing-specific structure.

• Scaling and cost characterization. PathWise's advantage grows with problem size (MRGI of 81.34% on the largest out-of-domain KP test set), but

Authors’ abstract

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.