mlsanityData to 14 Oct 2026

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

arXiv 2506.07972 ↗First posted 9 Jun 2025cs.LG cs.AI cs.CLcited by 21

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

Abstract (arXiv)

While Large Language Models (LLMs) have demonstrated significant advancements in reasoning and agent-based problem-solving, current evaluation methodologies fail to adequately assess their capabilities: existing benchmarks either rely on closed-ended questions prone to saturation and memorization, or subjective comparisons that lack consistency and rigor. In this work, we introduce HeuriGym, an agentic framework designed for evaluating heuristic algorithms generated by LLMs for combinatorial optimization problems, characterized by clearly defined objectives and expansive solution spaces. HeuriGym empowers LLMs to propose heuristics, receive evaluative feedback via code execution, and iteratively refine their solutions. We evaluate nine state-of-the-art models on nine problems across domains such as computer systems, logistics, and biology, exposing persistent limitations in tool use, planning, and adaptive reasoning. To quantify performance, we propose the Quality-Yield Index (QYI), a metric that captures both solution pass rate and quality. Even top models like GPT-o4-mini-high and Gemini-2.5-Pro attain QYI scores of only 0.6, well below the expert baseline of 1. Our open-source benchmark aims to guide the development of LLMs toward more effective and realistic problem-solving in scientific and engineering domains.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. Builds on 53 of its 168 references that are in the map. First posted on arXiv 9 Jun 2025.

Builds on

53 of 168 references.

References · 53

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  2. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  3. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,626
  4. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  5. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  6. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  7. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,182
  8. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  9. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,879
  10. 2020Learning to summarize from human feedbackcited by 2,588
  11. 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 2,004
  12. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,986
38 more
  1. 2020GShard: Scaling Giant Models with Conditional Computation and Automatic Shardingcited by 1,631
  2. 2022Competition-Level Code Generation with AlphaCodecited by 1,462
  3. 2023Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generationcited by 1,391
  4. 2019ZeRO: Memory Optimizations Toward Training Trillion Parameter Modelscited by 1,301
  5. 2021What Makes Good In-Context Examples for GPT-3?cited by 1,195
  6. 2024Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preferencecited by 1,184
  7. 2023Large Language Models as Optimizerscited by 864
  8. 2023PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallelcited by 660
  9. 2024BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructionscited by 546
  10. 2025Humanity's Last Examcited by 491
  11. 2024A Systematic Survey of Prompt Engineering in Large Language Models: Techniques and Applicationscited by 431
  12. 2024Training Language Models to Self-Correct via Reinforcement Learningcited by 426
  13. 2024ProcessBench: Identifying Process Errors in Mathematical Reasoningcited by 292
  14. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 276
  15. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 268
  16. 2023Self-Evaluation Guided Beam Search for Reasoningcited by 196
  17. 2022Self-Adaptive In-Context Learning: An Information Compression Perspective for In-Context Example Selection and Orderingcited by 161
  18. 2023NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptionscited by 135
  19. 2024OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Modelscited by 109
  20. 2025Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Designcited by 109
  21. 2024LLMOPT: Learning to Define and Solve General Optimization Problems from Scratchcited by 102
  22. 2024Open-Endedness is Essential for Artificial Superhuman Intelligencecited by 80
  23. 2023NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classescited by 79
  24. 2024HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMscited by 73
  25. 2025The Leaderboard Illusioncited by 66
  26. 2025No Free Labels: Limitations of LLM-as-a-Judge Without Human Groundingcited by 54
  27. 2024Commit0: Library Generation from Scratchcited by 52
  28. 2021BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessingcited by 50
  29. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 49
  30. 2024From Lists to Emojis: How Format Bias Affects Model Alignmentcited by 49
  31. 2024Towards Foundation Models for Mixed Integer Linear Programmingcited by 31
  32. 2021Equality Saturation for Tensor Graph Superoptimizationcited by 27
  33. 2024Self-Guiding Exploration for Combinatorial Problemscited by 22
  34. 2016Deep Multi-Species Embeddingcited by 20
  35. 2019A Deep Reinforcement Learning Approach for Global Routingcited by 20
  36. 2024Allo: A Programming Model for Composable Accelerator Designcited by 16
  37. 2023Slapo: A Schedule Language for Progressive Optimization of Large Deep Learning Model Trainingcited by 11
  38. 2021Automating Crystal-Structure Phase Mapping: Combining Deep Learning with Constraint Reasoningcited by 9

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 8; 2026: 13.

21 papers.

Sort:

By area:

  1. 2026CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discoverycited by 52
  2. 2025AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?cited by 27
  3. 2025FrontierCS: Evolving Challenges for Evolving Intelligencecited by 23
  4. 2025Autonomous Code Evolution Meets NP-Completenesscited by 15
  5. 2025A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solvingcited by 11
  6. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 7
  7. 2026G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Designcited by 7
  8. 2025Large Language Models in Operations Research: Methods, Applications, and Challengescited by 6
  9. 2026FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimizationcited by 6
  10. 2026Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolvecited by 5
  11. 2026FrontierSmith: Synthesizing Open-Ended Coding Problems at Scalecited by 3
  12. 2025Empowering Real-World: A Survey on the Technology, Practice, and Evaluation of LLM-driven Industry Agentscited by 2
9 more
  1. 2026QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Designcited by 1
  2. 2026AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worldscited by 1
  3. 2025Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Marketscited by 0
  4. 2026LLM Agents for Combinatorial Efficient Frontiers: Investment Portfolio Optimizationcited by 0
  5. 2026Heuristic Search as Language-Guided Program Optimizationcited by 0
  6. 2026Reinforcement Learning without Ground-Truth Solutions can Improve LLMscited by 0
  7. 2026LabBook: Harnessing Experimental History for Efficient LLM-Driven Discoverycited by 0
  8. 2026AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluationcited by 0
  9. 2026FDE-Bench: Evaluating End-to-End Delivery from Underspecified Real-World Business Requestscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization
  2. 2026PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs
  3. 2026DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization
  4. 2026Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization
  5. 2026SimpleEvol: An Agent-Loop Framework for LLM-Driven Automated Heuristic Design with Minimal Human Priors
  6. 2025OPT-BENCH: Evaluating LLM Agent on Large-Scale Search Spaces Optimization Problems
  7. 2025Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms
  8. 2025Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems