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

arXiv: https://arxiv.org/abs/2506.07972 · HTML: https://mlsanity.com/paper/2506.07972/

## 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.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 53)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://mlsanity.com/paper/1910.02054/) (2019)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel](https://mlsanity.com/paper/2304.11277/) (2023)
- [BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions](https://mlsanity.com/paper/2406.15877/) (2024)
- [Humanity's Last Exam](https://mlsanity.com/paper/2501.14249/) (2025)
- [A Systematic Survey of Prompt Engineering in Large Language Models: Techniques and Applications](https://mlsanity.com/paper/2402.07927/) (2024)
- [Training Language Models to Self-Correct via Reinforcement Learning](https://mlsanity.com/paper/2409.12917/) (2024)
- [ProcessBench: Identifying Process Errors in Mathematical Reasoning](https://mlsanity.com/paper/2412.06559/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Self-Adaptive In-Context Learning: An Information Compression Perspective for In-Context Example Selection and Ordering](https://mlsanity.com/paper/2212.10375/) (2022)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)

## Built on by (most cited first, 21 of 21)

- [CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discovery](https://mlsanity.com/paper/2604.01658/) (2026)
- [AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?](https://mlsanity.com/paper/2507.15887/) (2025)
- [FrontierCS: Evolving Challenges for Evolving Intelligence](https://mlsanity.com/paper/2512.15699/) (2025)
- [Autonomous Code Evolution Meets NP-Completeness](https://mlsanity.com/paper/2509.07367/) (2025)
- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2602.08253/) (2026)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization](https://mlsanity.com/paper/2605.25246/) (2026)
- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)
- [FrontierSmith: Synthesizing Open-Ended Coding Problems at Scale](https://mlsanity.com/paper/2605.14445/) (2026)
- [Empowering Real-World: A Survey on the Technology, Practice, and Evaluation of LLM-driven Industry Agents](https://mlsanity.com/paper/2510.17491/) (2025)
- [QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Design](https://mlsanity.com/paper/2607.11916/) (2026)
- [AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds](https://mlsanity.com/paper/2608.29397/) (2026)
- [Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets](https://mlsanity.com/paper/2509.13131/) (2025)
- [LLM Agents for Combinatorial Efficient Frontiers: Investment Portfolio Optimization](https://mlsanity.com/paper/2601.00770/) (2026)
- [Heuristic Search as Language-Guided Program Optimization](https://mlsanity.com/paper/2602.16038/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (2026)
- [LabBook: Harnessing Experimental History for Efficient LLM-Driven Discovery](https://mlsanity.com/paper/2610.00675/) (2026)
- [AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluation](https://mlsanity.com/paper/2610.03896/) (2026)
- [FDE-Bench: Evaluating End-to-End Delivery from Underspecified Real-World Business Requests](https://mlsanity.com/paper/2610.14539/) (2026)

## 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.