Skip to content

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

🕒 Published (v1): 2025-06-09 17:46 UTC · Source: Arxiv · Venue: ICLR 26 · link

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

HeuriGym is an agentic evaluation harness where LLMs iteratively generate, execute, and refine complete heuristic programs for nine novel combinatorial optimization (CO) problems spanning EDA, compilers, biology, and logistics. It introduces the Quality-Yield Index (QYI), a harmonic-mean metric over solution pass rate and quality relative to expert baselines. Even top models (GPT-o4-mini-high, Gemini-2.5-Pro) reach QYI ≈ 0.6 against an expert ceiling of 1.0.

Problem

Closed-ended benchmarks (HumanEval, AIME, GPQA) saturate rapidly and are vulnerable to data contamination; preference-based benchmarks (Chatbot Arena) lack rigorous quantitative grounding. Neither paradigm stresses iterative reasoning, adaptive tool use, or creative algorithm design on problems with astronomically large, constraint-heavy solution spaces.

Method

The framework presents each problem as a structured description (background, mathematical formalization in LaTeX, I/O format) and asks the LLM to generate a self-contained, executable heuristic program—no partial templates or scaffolded skeletons. Each generated program passes through a three-stage pipeline:

  • Stage I (Execution): compilation/interpretation succeeds, basic I/O completes.
  • Stage II (Solution Generation): non-empty output produced within a CPU/timeout budget.
  • Stage III (Verification): a domain-specific verifier checks constraint satisfaction; an evaluator scores the objective cost.

After each iteration, execution logs, verification diagnostics, and per-instance scores on a held-out demonstration set (~5 instances) are appended to the prompt, enabling iterative self-refinement over up to 10 rounds. The full evaluation set is withheld until the model stabilizes. Nine problems are drawn from low-citation literature (< 1,000 citations per problem's most-cited paper) to minimize memorization risk.

Metrics. Per-stage pass rate is captured by \(\text{SOLVEs}@i\), defined as the fraction of \(N\) instances passing stage \(s\) within \(i\) iterations. Solution quality relative to an expert baseline is: $\(\text{QUALITY} = \frac{1}{\hat{N}} \sum_{n=1}^{\hat{N}} \min\!\left(1,\, \frac{c_n^\star}{c_n}\right), \quad \text{YIELD} = \frac{\hat{N}}{N}\)$ where \(c_n\) and \(c_n^\star\) are LLM and expert costs, \(\hat{N}\) is the number of verified solutions. The unified Quality-Yield Index is their \(\beta=1\) harmonic mean: $\(\text{QYI} = \frac{2 \cdot \text{QUALITY} \cdot \text{YIELD}}{\text{QUALITY} + \text{YIELD}}\)$

Key Contributions

  • Open-source suite of nine novel CO problems (EDA, compilers, biology, logistics) with reproducible expert baselines and 218 evaluation instances.
  • End-to-end agentic harness: LLM generation → compilation/execution → domain verifier → evaluator → feedback-augmented prompt loop.
  • \(\text{SOLVEs}@i\) metric exposing which pipeline stage agents fail at across iterations.
  • QYI metric as a unified, F-score-style measure of agentic problem-solving over multi-round refinement.
  • Empirical study of nine SOTA models exposing persistent gaps in tool use, instruction fidelity, and adaptive reasoning.

Results

  • \(\text{SOLVE}_\text{III}@10\) (fraction of instances producing a verified feasible solution within 10 rounds): DeepSeek-V3 46.8%, DeepSeek-R1 73.4%, Gemini-2.5-Flash 67.4%, Gemini-2.5-Pro 65.1% (table truncated in source).
  • Top models GPT-o4-mini-high and Gemini-2.5-Pro achieve QYI ≈ 0.6 vs. expert baseline QYI = 1.0.
  • All evaluated models fall substantially below expert performance, confirming the benchmark is non-saturating for current SOTA.

Limitations

  • Initial suite of only nine problems; breadth remains limited.
  • Evaluation uses temperature = 0 for most models (o-series fixed at 1.0), which suppresses sampling diversity and may underestimate best-of-k capability.
  • Demonstration set is tiny (~5 instances); sensitivity to demo-set composition is not fully characterized.
  • The baseline agentic pipeline is intentionally minimal; no prompt-engineering or evolutionary strategies are applied, so reported numbers are floor estimates, not ceilings.
  • Private test sets not yet released; community holdout evaluation is deferred.

Relevance to Harnesses / Meta-Harnesses

HeuriGym is itself a textbook harness: it wraps LLM calls in a generate→execute→verify→score→prompt-augment loop, precisely the structure a meta-harness orchestrates. The design decision to partition data into a demo set (used inside the loop) and an evaluation set (held out) mirrors how production meta-harnesses separate exploration/feedback from final scoring. The \(\text{SOLVEs}@i\) metric is inherently harness-aware—it measures progress across loop iterations, not just final output—making it a directly transferable evaluation primitive for anyone building or benchmarking agentic harnesses. The framework's explicit separation of execution environment (CPU/memory limits, library versions in the system prompt) from the reasoning agent is a clean instantiation of the "tool-augmented reasoning" pattern central to harness design.