Skip to content

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

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Agentic benchmark for LLM-crafted heuristics in combinatorial optimization

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

HeuriGym is an agentic benchmark that evaluates LLMs on their ability to generate heuristic algorithms for combinatorial optimization (CO) problems from real scientific and engineering domains. It frames evaluation as an iterative loop—LLMs propose code, receive execution/verification feedback, and refine—avoiding both benchmark saturation and subjective judge-based evaluation. Even the best tested models (GPT-o4-mini-high, Gemini-2.5-Pro) reach only QYI ≈ 0.6 against an expert baseline of 1.0.

Problem

Existing LLM benchmarks suffer from two failure modes: (1) closed-ended benchmarks (AIME, HumanEval, GPQA) hit ceiling effects and are vulnerable to data contamination; (2) preference-based subjective benchmarks (Chatbot Arena) lack rigor and reward superficial features. Neither captures iterative reasoning, creative algorithm design, adaptive tool use, or large-solution-space exploration—core capabilities required in real-world scientific and engineering problem-solving.

Method

HeuriGym presents LLMs with structured descriptions of nine novel combinatorial optimization problems (background, LaTeX-formalized objective, I/O spec), then runs a feedback loop across up to 10 iterations: 1. Stage I – Execution: LLM generates a complete Python or C++ heuristic implementation (no scaffolding or partial templates); it must compile/interpret and perform I/O. 2. Stage II – Solution Generation: The program must produce a non-empty, correctly formatted output within a CPU/time budget. 3. Stage III – Verification: A problem-specific verifier checks constraint satisfaction; a cost evaluator scores solution quality against expert baselines.

Execution logs, verification outcomes, and objective scores on a small demonstration set (~5 instances) are appended to the prompt for the next iteration. Problems are selected to have fewer than 1,000 citations on Google Scholar (reducing memorization risk), large solution spaces, and scalable instance sets (demo vs. evaluation split).

To quantify performance, the paper introduces: - \(\text{SOLVEs}@i\): fraction of instances passing stage \(s\) within \(i\) iterations - \(\text{Quality} = \frac{1}{\hat{N}}\sum_{n=1}^{\hat{N}} \min\!\left(1, \frac{c_n^\star}{c_n}\right)\) (ratio of expert cost to LLM cost, capped at 1) - \(\text{Yield} = \hat{N}/N\) (fraction of instances producing a verified feasible solution) - \(\text{QYI} = \frac{(1+\beta^2)\cdot\text{Quality}\cdot\text{Yield}}{\beta^2\cdot\text{Quality}+\text{Yield}}\) (harmonic mean, \(\beta=1\) by default)

Key Contributions

  • Nine-problem open-source CO benchmark spanning EDA (operator scheduling, technology mapping, global routing, e-graph extraction), compilers (intra-operator parallelism), computational biology (protein sequence design, Mendelian error detection), and logistics (airline crew pairing, pickup-and-delivery with time windows), each with expert baselines and private test sets.
  • End-to-end agentic framework: iterative LLM → code execution → verification → feedback loop, requiring full program synthesis without templates or algorithmic hints.
  • New metrics SOLVEs@i and QYI that jointly capture iteration-stage pass rates, solution feasibility yield, and solution quality relative to expert heuristics.
  • Empirical study of nine state-of-the-art LLMs exposing systematic deficits in tool use, multi-step planning, instruction fidelity, and iterative refinement.

Results

  • SOLVE\(_\text{III}\)@10 (verified feasible solution within 10 iterations): GPT-o4-mini-high 74.8%, DeepSeek-R1 73.4%, Gemini-2.5-Flash 67.4%, Gemini-2.5-Pro 65.1%, Claude-3.7-Sonnet 60.1%, Qwen3-235B 45.9%, DeepSeek-V3 46.8%, LLaMA-4-Maverick 35.8%, LLaMA-3.3 33.9%.
  • QYI for top models (GPT-o4-mini-high, Gemini-2.5-Pro): ≈ 0.6, versus expert baseline of 1.0—a 40% gap.
  • Solution spaces in some tasks exceed \(10^{65{,}000}\) (intra-operator parallelism), making exhaustive search infeasible and ruling out commercial ILP solvers.
  • Benchmark covers 218 evaluation instances across nine tasks; private test sets reserved for future leakage-resistant evaluation.

Limitations

  • Nine problems may not fully cover the breadth of real-world CO; adding problems requires community effort and adherence to strict selection criteria.
  • Expert baselines are problem-specific heuristics, not provably optimal solutions, so QYI > 1 is possible but not systematically explored.
  • Evaluation is Python-only in the main experiments (C++ support mentioned but not detailed in results), which may artificially constrain runtime performance.
  • Fixed temperature (0 for most models) and single agentic pipeline represent baseline conditions; more advanced prompting strategies (chain-of-thought, evolutionary search) are left to future work.
  • Citation-count proxy (<1,000) for "limited exposure" is imperfect; some problems may still appear in training data.
  • Private test sets have not yet been released, so current results are only on the public evaluation split.

Relevance to Agentic AI / LLM Agents

HeuriGym directly operationalizes the agentic loop—generate, execute, observe, refine—as a rigorous benchmark, filling a critical gap where existing evaluations either saturate quickly or lack objective metrics. The four dimensions it probes (tool-augmented reasoning, multi-step planning, instruction fidelity, iterative refinement) map directly onto the core competencies debated in the agentic AI community. The QYI metric is broadly applicable to any domain where LLM agents produce executable artifacts evaluated against quantitative targets, providing a template for how to measure agent capability beyond pass/fail. The finding that even top frontier models reach only QYI ≈ 0.6 on novel CO problems provides a calibrated, contamination-resistant data point on where the frontier of agentic reasoning currently stands.