Technische Samenvatting: PathWise

Probleemstelling

Geautomatiseerd Heuristisch Ontwerp (AHD) heeft tot doel om automatisch heuristische algoritmen te genereren voor Combinatorische Optimalisatieproblemen (COP's), waardoor de afhankelijkheid van handmatig, door experts ontworpen designs wordt verminderd. Hoewel Groot Taalmodellen (LLM's) recentelijk AHD mogelijk hebben gemaakt door integratie in evolutionaire zoekprocessen, kampen bestaande frameworks met aanzienlijke beperkingen. Populatie-gebaseerde methoden vertrouwen vaak op vaste evolutionaire regels en statische prompt-sjablonen, wat leidt tot een kortzichtige heuristische generatie, redundante evaluaties en voortijdige convergentie. Boom-gebaseerde methoden, zoals die gebruikmaken van Monte Carlo Boom Zoeken (MCTS), leggen hiërarchische structuren op die gedreven worden door prestatiestatistieken in plaats van semantisch begrip van het zoeklandschap. Cruciaal is dat huidige benaderingen een stateful, semantische representatie missen van hoe heuristieken worden afgeleid, hoe bewerkingen zich over generaties voortplanten, of waarom modificaties slagen of falen. Dit resulteert in een inefficiënt gebruik van LLM-aanroepen en een falen om eerdere beslissingen effectief mee te nemen.

Methodologie

De auteurs stellen PathWise voor (Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs), een innovatief multi-agent redeneringskader dat heuristische generatie formuleert als een sequentieel besluitvormingsproces over een entailment-graf. Deze graf dient als een compacte, stateful geheugenopslag van de zoektrajectorie.

Kerncomponenten

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

   • In tegenstelling tot standaard evolutionaire bomen of populaties, codeert de entailment-graf de afleidingsgeschiedenis.
   • Knopen ($v$): Representeren tuples die heuristische code ($h$), een natuurlijke taal-afleidingsrationalisatie ($\kappa$), een algoritmische beschrijving ($d$), prestatie-metrics ($P(h; D)$) en parent-metadata ($PM$) bevatten.
   • Randen ($E$): Verbinden parent-sets met child-knopen en coderen de specifieke rationalisatie die werd gebruikt om het kind af te leiden van zijn ouders.
   • Deze structuur stelt het systeem in staat om toekomstige beslissingen te conditioneren op de afleidingsgeschiedenis in plaats van stappen te behandelen als geïsoleerde steekproeven.

2. Multi-Agent Systeem:
   Het kader opereert via een gecoördineerde cyclus van planning, uitvoering en reflectie over twee tijdschalen (buitenste populatie-updates en binnenste entailment-stappen):

   • Policy Agent ($\pi_p$): Treedt op als een hoog-niveau planner. Deze observeert de huidige staat (de entailment-graf frontier) en stelt acties voor die worden gedefinieerd door een tuple van geselecteerde parent-knopen ($S$) en een natuurlijke taal-afleidingsrationalisatie ($\kappa$). Dit stelt de policy in staat om dynamisch nieuwe operator-types te bedenken in plaats van te vertrouwen op vaste sjablonen.
   • World Model Agent ($\pi_{wm}$): Treedt op als een laag-niveau uitvoerder. Deze vertaalt de hoog-niveau acties van de policy naar uitvoerbare heuristische code (rollouts) geconditioneerd op de geselecteerde ouders en de instructie.
   • Critic Agents:
     • Policy Critic ($\pi_{p\_critic}$): Analyseert de uitkomsten van policy-acties (parent-selecties en instructies) om gerouteerde reflecties te leveren die toekomstige evolutionaire strategieën sturen.
     • World Model Critic ($\pi_{wm\_critic}$): Vergelijkt de best en slechtst presterende heuristische rollouts om feedback te geven over de kwaliteit van code-synthese, waarmee het world model wordt gestuurd om de algoritmische structuur en efficiëntie te verfijnen.

3. Zoekproces:

   • Buitenste Lus: Onderhoudt een populatie van root-knopen.
   • Binnenste Lus: Construeert incrementeel een entailment-graf geworteld in de huidige populatie. Bij elke stap steekt het systeem meerdere acties en rollouts, selecteert de best resulterende knoop, en update de graf.
   • Diversiteitsmechanismen: Om outputs met lage diversiteit te voorkomen, hanteert PathWise Prompt-Level Diversiteit (perturberen van prompts met exploratieve zinsdelen) en State Shuffling (randomiseren van knoopvolgorde om positionele bias te mitigeren).

Belangrijkste Bijdragen

1. Hybride Graf-Populatie Formulering: De auteurs introduceren een formulering waarbij een entailment-graf afleidingsrationalisatie en prestatiegeschiedenis codeert, dienend als een gedeelde staat voor interactie tussen policy en world model.
2. Gecoördineerd Multi-Agent Kader: Een systeem waarbij een policy agent de evolutionaire strategie controleert, een world model code-generatie uitvoert, en critic agents gerouteerde reflecties leveren, wat zelf-evoluerende, state-aware heuristische generatie mogelijk maakt zonder LLM-parameters bij te werken.
3. Prompt-Level Diversiteit: Mechanismen om variatie te garanderen in parent-selectie en heuristische rollouts, waardoor bredere exploratie over de entailment-graf mogelijk wordt.
4. Empirische Validatie: Uitgebreide experimenten die aantonen dat PathWise sterkere heuristieken ontdekt met minder evaluaties, snellere convergentie bereikt, en effectief schaalt naar grotere probleemgroottes over diverse COP's.

Experimentele Resultaten

PathWise werd geëvalueerd op meerdere NP-hard COP's, waaronder het Traveling Salesman Problem (TSP), Knapsack Problem (KP), Capacitated Vehicle Routing Problem (CVRP), Multiple Knapsack Problem (MKP), Orienteering Problem (OP) en Bin Packing Problem (BPP). Het kader werd getest over drie zoekparadigma's: Stap-voor-Stap Constructie, Ant Colony Optimization (ACO) en Guided Local Search (GLS).

• Prestaties: PathWise presteerde consequent beter dan state-of-the-art LLM-gebaseerde AHD-baselines (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) en handmatig ontworpen heuristieken. Het bereikte lagere optimaliteitsgaten over zowel in-domein als out-of-domein testsets.
• Efficiëntie: PathWise convergeerde sneller naar betere heuristieken. In meerdere experimenten bereikte PathWise superieure prestaties met slechts 500 evaluaties, terwijl baselines 1000 evaluaties mochten uitvoeren.
• Schaalbaarheid: De methode toonde sterke generalisatie naar grotere probleemgroottes (bijv. TSP met $N=200$, KP met $N=500$) en verschillende LLM-backbones (GPT-4o-mini, GPT-5-nano met variërende redeneringsniveaus).
• Ablatie Studies: Het verwijderen van critic agents of diversiteitsmechanismen degradeerde de prestaties aanzienlijk, wat de noodzaak bevestigt van state-aware feedback en exploratie.

Betekenis en Aanspraken

Het artikel beweert dat PathWise een verschuiving vertegenwoordigt van "trial-and-error evolutie" naar "state-aware planning door redenering". Door heuristische ontdekking te behandelen als een sequentieel besluitvormingsproces over een entailment-graf, kan het systeem eerdere beslissingen meenemen en afleidingsinformatie over generaties opnieuw gebruiken of vermijden.

De auteurs benadrukken dat PathWise trainingsvrij is in de zin dat het geen LLM-parameters bijwerkt; in plaats daarvan maakt het gebruik van de voorgeprende kennis van LLM's, versterkt door natuurlijke taal-reflecties. De betekenis ligt in het vermogen om de kortzichtigheid van bestaande AHD-methoden te overwinnen door een gestructureerd geheugen van het zoekproces te bieden, waardoor redundante evaluaties worden verminderd en effectievere ontdekking van hoogwaardige heuristieken voor complexe combinatorische problemen mogelijk wordt. Het werk suggereert dat gestructureerd redeneren over afleidingsgeschiedenis een kritiek component is voor het schalen van LLM-gebaseerd geautomatiseerd algoritme-ontwerp.