Technical Summary: PathWise

Problem Statement

Automated Heuristic Design (AHD) aims to automatically generate heuristic algorithms for Combinatorial Optimization Problems (COPs), reducing reliance on manual, expert-crafted designs. While Large Language Models (LLMs) have recently enabled AHD by integrating into evolutionary search processes, existing frameworks suffer from significant limitations. Population-based methods often rely on fixed evolutionary rules and static prompt templates, leading to myopic heuristic generation, redundant evaluations, and premature convergence. Tree-based methods, such as those using Monte Carlo Tree Search (MCTS), impose hierarchical structures driven by performance statistics rather than semantic understanding of the search landscape. Crucially, current approaches lack a stateful, semantic representation of how heuristics are derived, how edits propagate across generations, or why modifications succeed or fail. This results in inefficient use of LLM calls and a failure to carry forward past decisions effectively.

Methodology

The authors propose PathWise (Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs), a novel multi-agent reasoning framework that formulates heuristic generation as a sequential decision process over an entailment graph. This graph serves as a compact, stateful memory of the search trajectory.

Core Components

1. Entailment Graph ($G = (V, E)$):

   • Unlike standard evolutionary trees or populations, the entailment graph encodes the derivation history.
   • Nodes ($v$): Represent tuples containing heuristic code ($h$), a natural-language derivation rationale ($\kappa$), an algorithmic description ($d$), performance metrics ($P(h; D)$), and parent metadata ($PM$).
   • Edges ($E$): Connect parent sets to child nodes, encoding the specific rationale used to derive the child from its parents.
   • This structure allows the system to condition future decisions on derivation history rather than treating steps as isolated sampling events.

2. Multi-Agent System:
   The framework operates via a coordinated cycle of planning, execution, and reflection across two timescales (outer population updates and inner entailment steps):

   • Policy Agent ($\pi_p$): Acts as a high-level planner. It observes the current state (the entailment graph frontier) and proposes actions defined by a tuple of selected parent nodes ($S$) and a natural-language derivation rationale ($\kappa$). This allows the policy to dynamically invent new operator types rather than relying on fixed templates.
   • World Model Agent ($\pi_{wm}$): Acts as a low-level executor. It translates the policy's high-level actions into executable heuristic code (rollouts) conditioned on the selected parents and the directive.
   • Critic Agents:
     • Policy Critic ($\pi_{p\_critic}$): Analyzes the outcomes of policy actions (parent selections and directives) to provide routed reflections that guide future evolutionary strategies.
     • World Model Critic ($\pi_{wm\_critic}$): Compares the best and worst performing heuristic rollouts to provide feedback on code synthesis quality, guiding the world model to refine algorithmic structure and efficiency.

3. Search Process:

   • Outer Loop: Maintains a population of root nodes.
   • Inner Loop: Incrementally constructs an entailment graph rooted at the current population. At each step, the system samples multiple actions and rollouts, selects the best resulting node, and updates the graph.
   • Diversity Mechanisms: To prevent low-diversity outputs, PathWise employs Prompt-Level Diversity (perturbing prompts with exploratory phrases) and State Shuffling (randomizing node order to mitigate positional bias).

Key Contributions

1. Hybrid Graph-Population Formulation: The authors introduce a formulation where an entailment graph encodes derivation rationale and performance history, serving as a shared state for policy and world model interaction.
2. Coordinated Multi-Agent Framework: A system where a policy agent controls evolutionary strategy, a world model executes code generation, and critic agents provide routed reflections, enabling self-evolving, state-aware heuristic generation without updating LLM parameters.
3. Prompt-Level Diversity: Mechanisms to ensure variety in parent selection and heuristic rollouts, enabling broader exploration over the entailment graph.
4. Empirical Validation: Extensive experiments demonstrating that PathWise discovers stronger heuristics with fewer evaluations, achieves faster convergence, and scales effectively to larger problem sizes across diverse COPs.

Experimental Results

PathWise was evaluated on multiple NP-hard COPs, including the Traveling Salesman Problem (TSP), Knapsack Problem (KP), Capacitated Vehicle Routing Problem (CVRP), Multiple Knapsack Problem (MKP), Orienteering Problem (OP), and Bin Packing Problem (BPP). The framework was tested across three search paradigms: Step-by-Step Construction, Ant Colony Optimization (ACO), and Guided Local Search (GLS).

• Performance: PathWise consistently outperformed state-of-the-art LLM-based AHD baselines (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) and manually designed heuristics. It achieved lower optimality gaps across both in-domain and out-of-domain test sets.
• Efficiency: PathWise converged faster to better heuristics. In several experiments, PathWise achieved superior performance with only 500 evaluations, whereas baselines were allowed 1000 evaluations.
• Scalability: The method demonstrated strong generalization to larger problem sizes (e.g., TSP with $N=200$, KP with $N=500$) and different LLM backbones (GPT-4o-mini, GPT-5-nano with varying reasoning levels).
• Ablation Studies: Removing critic agents or diversity mechanisms significantly degraded performance, confirming the necessity of state-aware feedback and exploration.

Significance and Claims

The paper claims that PathWise represents a shift from "trial-and-error evolution" toward "state-aware planning through reasoning." By treating heuristic discovery as a sequential decision process over an entailment graph, the system can carry forward past decisions and reuse or avoid derivation information across generations.

The authors emphasize that PathWise is training-free in the sense that it does not update LLM parameters; instead, it leverages the pretrained knowledge of LLMs reinforced through natural-language reflections. The significance lies in its ability to overcome the myopia of existing AHD methods by providing a structured memory of the search process, thereby reducing redundant evaluations and enabling more effective discovery of high-quality heuristics for complex combinatorial problems. The work suggests that structured reasoning over derivation history is a critical component for scaling LLM-based automated algorithm design.