Technische Samenvatting: HeuriGym: Een Agentic Benchmark voor door LLM's gecreëerde Heuristieken in Combinatorische Optimalisatie

Probleemstelling

Huidige evaluatiemethodologieën voor Large Language Models (LLM's) kampen met een dubbele crisis bij het beoordelen van hun probleemoplossende vermogens. Ten eerste zijn op grondwaarheid gebaseerde objectieve benchmarks (bijv. AIME, HumanEval) afhankelijk van gesloten vragen die vatbaar zijn voor datacontaminatie en prestatiesaturatie, waardoor ze niet in staat zijn om realistische scenario's te reflecteren waar oplossingen niet uniek of vooraf gedefinieerd zijn. Ten tweede introduceren op oordeel-voorkeur gebaseerde subjectieve evaluaties (bijv. Chatbot Arena) een hoge variantie en geven ze vaak de voorkeur aan oppervlakkige factoren boven substantiële redeneerkwaliteit.

Er is een kritieke kloof in de evaluatie van de vraag of LLM's verder kunnen gaan dan patroonherkenning om echte probleemoplossende vindingrijkheid te tonen in complexe, iteratieve engineering-workflows. Specifiek hebben bestaande benchmarks moeite met het beoordelen van het vermogen om nieuwe heuristieken te ontwerpen voor combinatorische optimalisatieproblemen (CO), die vereisen dat men door enorme oplossingsruimten navigeert, strikte beperkingen naleeft en strategieën aanpast op basis van runtime-feedback.

Methodologie

De auteurs introduceren HeuriGym, een agentic framework ontworpen om LLM's te evalueren op hun vermogen om heuristische algoritmen voor combinatorische optimalisatieproblemen te genereren, uit te voeren en iteratief te verfijnen.

Framework Overzicht

HeuriGym werkt via een interactieve agentic loop bestaande uit drie stadia:

1. Probleembeschrijving: De LLM ontvangt een gestructureerde prompt met een natuurlijke taal achtergrond, een wiskundige formalisering van het doel en de beperkingen, en specifieke input/output bestandsformaten. In tegenstelling tot eerder werk dat gedeeltelijke implementaties of scaffolds biedt, levert HeuriGym alleen de functie-interface, waardoor de LLM datastructuren en algoritmen vanaf nul moet ontwerpen.
2. Executie en Verificatie: De gegenereerde code wordt gecompileerd of geïnterpreteerd binnen een gesandboxed omgeving. Een domeinspecifieke verifieerder controleert de naleving van beperkingen (bijv. behoud van afhankelijkheden), terwijl een evaluator de kosten berekent op basis van het optimalisatiedoel.
3. Iteratieve Verfijning: Executielogs, verificieresultaten en prestatie-metrieken van een kleine demonstratieset worden aan de prompt toegevoegd. Deze feedbackloop stelt de LLM in staat om fouten te debuggen, schendingen van beperkingen te corrigeren en zijn heuristische strategieën over meerdere iteraties te verfijnen.

Benchmark Constructie

De benchmark bestaat uit negen combinatorische optimalisatieproblemen die variëren van computersystemen en logistiek tot computationele biologie (bijv. operator scheduling, technology mapping, airline crew pairing, eiwitsequentieontwerp).

• Selectiecriteria: Problemen werden geselecteerd op basis van beperkte blootstelling in de literatuur (minder dan 1.000 citaties voor het meest geciteerde artikel) om risico's op memorisatie te minimaliseren. Ze kenmerken zich door goed gedefinieerde natuurlijke taal specificaties, grote oplossingsruimten en schaalbare data-instanties.
• Dataset: Elk probleem bevat een kleine demonstratieset (~5 instanties) voor few-shot prompting en iteratieve verfijning, en een grotere evaluatieset (tientallen instanties) voor de uiteindelijke test.

Evaluatie Metrieken

Om de beperkingen van standaard metrieken zoals PASS@k aan te pakken, stellen de auteurs de volgende voor:

• SOLVEs@i: Houdt de waarschijnlijkheid bij van het oplossen van een beperkt probleem binnen $i$ iteraties, waarbij het succes in drie stadia wordt gemeten: Executie (Stadium I), Oplossing Generatie (Stadium II) en Verificatie (Stadium III).
• Quality-Yield Index (QYI): Een uniforme metriek gedefinieerd als het harmonisch gemiddelde van Quality (hoe dicht de oplossing bij een expert-baseline ligt) en Yield (het aandeel instanties dat de verificatie passeert).
  • $Quality = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, waarbij $c_n$ de kosten van de LLM zijn en $c^*_n$ de kosten van de expert zijn.
  • $Yield = \frac{\hat{N}}{N}$, waarbij $\hat{N}$ het aantal geverifieerde oplossingen is.
  • $QYI = \frac{(1 + \beta^2) \cdot Quality \cdot Yield}{(\beta^2 \cdot Quality) + Yield}$ (met $\beta=1$).

Belangrijkste Resultaten

De auteurs hebben negen state-of-the-art modellen (inclusief GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1, en LLaMA-varianten) geëvalueerd op de HeuriGym benchmark.

• Prestatiekloof: Zelfs topmodellen worstelen met het bereiken van expert-niveau prestaties. Het best presterende model, Gemini-2.5-Pro, behaalde een QYI-score van ongeveer 0,62, wat aangeeft dat de oplossingen gemiddeld slechts 60% zo effectief zijn als door experts gecreëerde heuristieken. Andere modellen scoorden aanzienlijk lager (bijv. LLaMA-3.3 en LLaMA-4-Maverick onder de 0,30).
• Iteratieve Verbetering: Het verhogen van het aantal iteraties verbetert de prestaties aanzienlijk. Bijvoorbeeld, het succespercentage van GPT-o4-mini-high steeg van 53,2% bij iteratie 1 naar 74,8% bij iteratie 10, wat het belang van iteratieve verfijning benadrukt.
• Foutmodi: Analyse onthulde veelvoorkomende fouttypen, waaronder gehallucineerde API's, onjuiste algoritmische logica, misverstanden over beperkingen en time-outs.
• Evolutionaire Frameworks: Standaard evolutionaire zoekframeworks (bijv. ReEvo, HSEvo) presteerden slecht vergeleken met het baseline model, omdat ze vaak er niet in slaagden executie-feedback effectief te incorporeren en de context over iteraties heen braken.

Betekenis en Bijdragen

Het artikel claimt drie primaire bijdragen:

1. Een Open-Source Benchmark Suite: Een collectie van negen realistische, impactvolle combinatorische optimalisatieproblemen die vermogen tot meerstaps redeneren en algoritmisch ontwerp evalueren, waarmee verder wordt gekeken dan gememoriseerde patronen.
2. Een End-to-End Agentic Framework: Een systeem dat oplossing generatie, automatische verificatie en iteratieve verfijning ondersteunt, dienend als een testbed voor geavanceerde prompting technieken en evolutionaire strategieën.
3. Empirische Inzichten: Een uitgebreide studie die onthult dat huidige LLM's, ondanks hun redeneer vermogens, hardnekkige beperkingen ervaren in toolgebruik, planning en adaptief redeneren wanneer ze worden toegepast op complexe, real-world wetenschappelijke en technische problemen.

De auteurs positioneren HeuriGym als een noodzakelijke stap naar het leiden van LLM-ontwikkeling richting effectievere, realistische probleemoplossing in domeinen waar optimale oplossingen alleen tractabel zijn voor kleine instanties en waar de ontdekking van heuristieken essentieel is. De benchmark beoogt de kloof tussen huidige modelcapaciteiten en de eisen van praktische engineering-workflows bloot te leggen, wat de ontwikkeling stimuleert van modellen die in staat zijn tot echte heuristische uitvinding in plaats van louter patroonherkenning.