Research map / Multi-agent systems and games / LLM agents

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

ICML 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent collaboration and safety · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes PathWise, a training-free multi-agent LLM framework that plans heuristic evolution as a sequential decision process over an entailment graph with policy, world model, and critic agents, outperforming LLM-based AHD baselines on TSP, KP, CVRP, MKP, OP and BPP.

Problem

Existing LLM-based automated heuristic design (AHD) methods use fixed evolutionary rules and static prompts, causing myopic generation, redundant evaluations, and no stateful memory of how heuristics were derived.

Approach

Formulates heuristic generation as an MDP over an entailment graph that stores derivation rationale, parent metadata and performance; a policy agent plans parent selection and directives, a world model agent generates heuristic rollouts, and two critic agents give routed verbal reflections, with prompt-level diversity via exploration phrases and state shuffling.

Key results

• On TSP with GPT-5-nano (medium), PathWise reaches 8.41% gap at N=50 versus 9.69% for the best LLM baseline MCTS-AHD in the constructive framework.
• PathWise reports a mean relative gap improvement of 20.38% on TSP averaged over test sets and backbones in the constructive framework, and 49.89% on KP with GPT-4o-mini.
• In the ACO framework, PathWise achieves average MRGI gains of 60.22% on TSP and 89.35% on MKP over LLM-based AHD baselines.

Surprising findings

• Removing both critic agents degrades TSP gap from 9.72% to 14.85% on the validation TSP50 set, a larger drop than removing either critic alone.

Limitations

• Relies on proprietary GPT models accessed via API, so reproducibility depends on model availability.
• Evaluated only on synthetic instance distributions and three search frameworks.

Experimental setup

Datasets: synthetic COP instances (TSP, KP, CVRP, MKP, OP, BPP)

Benchmarks: TSP KP CVRP MKP OP offline BPP online BPP

Metrics: objective value optimality gap

Baselines: Greedy Construct POMO ACO DeepACO FunSearch EoH ReEvo HSEvo MCTS-AHD

Builds on: FunSearch EoH ReEvo HSEvo MCTS-AHD

Closest papers by meaning

• SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.90)
• SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.89)
• SE-Agent: Self-Evolution Trajectory Optimization in Multi-Step Reasoning with LLM-Based Agents (NeurIPS 2025 · similarity 0.89)
• Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.88)
• Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.88)
• Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies (NeurIPS 2026 · similarity 0.88)