Technical Summary: HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization

Problem Statement

Current evaluation methodologies for Large Language Models (LLMs) face a dual crisis in assessing their problem-solving capabilities. First, ground-truth-based objective benchmarks (e.g., AIME, HumanEval) rely on closed-ended questions that are susceptible to data contamination and performance saturation, failing to reflect real-world scenarios where solutions are not unique or predefined. Second, judge-preference-based subjective evaluations (e.g., Chatbot Arena) introduce high variance and often prioritize superficial factors over substantive reasoning quality.

There is a critical gap in evaluating whether LLMs can move beyond pattern recognition to exhibit genuine problem-solving ingenuity in complex, iterative engineering workflows. Specifically, existing benchmarks struggle to assess the ability to design novel heuristics for combinatorial optimization (CO) problems, which require navigating vast solution spaces, adhering to strict constraints, and adapting strategies based on runtime feedback.

Methodology

The authors introduce HeuriGym, an agentic framework designed to evaluate LLMs on their ability to generate, execute, and iteratively refine heuristic algorithms for combinatorial optimization problems.

Framework Overview

HeuriGym operates through an interactive agentic loop consisting of three stages:

1. Problem Description: The LLM receives a structured prompt containing a natural language background, a mathematical formalization of the objective and constraints, and specific input/output file formats. Unlike prior work that provides partial implementations or scaffolds, HeuriGym provides only the function interface, requiring the LLM to design data structures and algorithms from scratch.
2. Execution and Verification: The generated code is compiled or interpreted within a sandboxed environment. A domain-specific verifier checks constraint satisfaction (e.g., dependency preservation), while an evaluator calculates the cost based on the optimization objective.
3. Iterative Refinement: Execution logs, verification outcomes, and performance metrics from a small demonstration set are appended to the prompt. This feedback loop allows the LLM to debug errors, correct constraint violations, and refine its heuristic strategies over multiple iterations.

Benchmark Construction

The benchmark comprises nine combinatorial optimization problems spanning computer systems, logistics, and computational biology (e.g., operator scheduling, technology mapping, airline crew pairing, protein sequence design).

• Selection Criteria: Problems were selected to have limited exposure in literature (fewer than 1,000 citations for the most-cited paper) to minimize memorization risks. They feature well-defined natural language specifications, large solution spaces, and scalable data instances.
• Dataset: Each problem includes a small demonstration set (~5 instances) for few-shot prompting and iterative refinement, and a larger evaluation set (dozens of instances) for final testing.

Evaluation Metrics

To address the limitations of standard metrics like PASS@k, the authors propose:

• SOLVEs@i: Tracks the probability of solving a constrained problem within $i$ iterations, measuring success in passing three stages: Execution (Stage I), Solution Generation (Stage II), and Verification (Stage III).
• Quality-Yield Index (QYI): A unified metric defined as the harmonic mean of Quality (how close the solution is to an expert baseline) and Yield (the proportion of instances passing verification).
  • $Quality = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, where $c_n$ is the LLM cost and $c^*_n$ is the expert cost.
  • $Yield = \frac{\hat{N}}{N}$, where $\hat{N}$ is the number of verified solutions.
  • $QYI = \frac{(1 + \beta^2) \cdot Quality \cdot Yield}{(\beta^2 \cdot Quality) + Yield}$ (with $\beta=1$).

Key Results

The authors evaluated nine state-of-the-art models (including GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1, and LLaMA variants) on the HeuriGym benchmark.

• Performance Gap: Even top-tier models struggle to achieve expert-level performance. The best-performing model, Gemini-2.5-Pro, achieved a QYI score of approximately 0.62, indicating its solutions are, on average, only 60% as effective as expert-crafted heuristics. Other models scored significantly lower (e.g., LLaMA-3.3 and LLaMA-4-Maverick below 0.30).
• Iterative Improvement: Increasing the number of iterations significantly improves performance. For instance, GPT-o4-mini-high's success rate (SOLVEIII) rose from 53.2% at iteration 1 to 74.8% at iteration 10, highlighting the importance of iterative refinement.
• Failure Modes: Analysis revealed common failure types, including hallucinated APIs, incorrect algorithmic logic, misunderstanding of constraints, and timeouts.
• Evolutionary Frameworks: Standard evolutionary search frameworks (e.g., ReEvo, HSEvo) performed poorly compared to the baseline model, often failing to incorporate execution feedback effectively and breaking context across iterations.

Significance and Contributions

The paper claims three primary contributions:

1. An Open-Source Benchmark Suite: A collection of nine realistic, high-impact combinatorial optimization problems that evaluate multi-step reasoning and algorithmic design capabilities, moving beyond memorized patterns.
2. An End-to-End Agentic Framework: A system supporting solution generation, automated verification, and iterative refinement, serving as a testbed for advanced prompting techniques and evolutionary strategies.
3. Empirical Insights: A comprehensive study revealing that current LLMs, despite their reasoning capabilities, face persistent limitations in tool use, planning, and adaptive reasoning when applied to complex, real-world scientific and engineering problems.

The authors position HeuriGym as a necessary step toward guiding LLM development toward more effective, realistic problem-solving in domains where optimal solutions are tractable only for small instances and where heuristic discovery is essential. The benchmark aims to expose the gap between current model capabilities and the demands of practical engineering workflows, encouraging the development of models capable of genuine heuristic invention rather than mere pattern matching.