# AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design

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

## Key facts

- Cited by 3 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 48 of its 76 references that are in the map.
- First posted on arXiv 9 May 2026.

## 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 48)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [RT-2: Vision-Language-Action Models Transfer Web Knowledge to Robotic Control](https://mlsanity.com/paper/2307.15818/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [CodeAgent: Enhancing Code Generation with Tool-Integrated Agent Systems for Real-World Repo-level Coding Challenges](https://mlsanity.com/paper/2401.07339/) (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)
- [Mobile-Agent-v2: Mobile Device Operation Assistant with Effective Navigation via Multi-Agent Collaboration](https://mlsanity.com/paper/2406.01014/) (2024)
- [You Only Look at Screens: Multimodal Chain-of-Action Agents](https://mlsanity.com/paper/2309.11436/) (2023)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [Cradle: Empowering Foundation Agents Towards General Computer Control](https://mlsanity.com/paper/2403.03186/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [Kevin: Multi-Turn RL for Generating CUDA Kernels](https://mlsanity.com/paper/2507.11948/) (2025)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [The Dawn of GUI Agent: A Preliminary Case Study with Claude 3.5 Computer Use](https://mlsanity.com/paper/2411.10323/) (2024)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning](https://mlsanity.com/paper/2504.05108/) (2025)
- [Large Language Models can be Guided to Evade AI-Generated Text Detection](https://mlsanity.com/paper/2305.10847/) (2023)

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

- [Policy and World Modeling Co-Training for Language Agents](https://mlsanity.com/paper/2606.02388/) (2026)
- [Cooperative Coevolution for Resource-Constrained Agentic LLM Post-Training](https://mlsanity.com/paper/2608.02391/) (2026)
- [From Search to Signal: Online Post-Training in Automatic Heuristic Design](https://mlsanity.com/paper/2609.39383/) (2026)

## Abstract (arXiv)

Automatic heuristic design (AHD) has emerged as a promising paradigm for solving NP-hard combinatorial optimization problems (COPs). Recent works show that large language models (LLMs), when integrated into well-designed frameworks (i.e., LLM-AHD), can autonomously discover high-performing heuristics. However, existing LLM-AHD frameworks typically treat LLMs as passive generators within fixed workflows, where the model generates heuristics from manually designed, limited context. Such context may fail to capture state-dependent information (e.g., specific failure modes), leading to inefficient trial-and-error exploration. To overcome these limitations, we propose AHD Agent, a novel tool-integrated, multi-turn framework that empowers LLMs to proactively decide whether to generate heuristics or invoke tools to retrieve targeted evidence from the solving environment. To effectively train such a dynamic decision-making agent, we introduce an agentic reinforcement learning (RL) system, which leverages a novel environment synthesis pipeline to optimize a compact model's generalizable AHD capabilities. Experiments across eight diverse domains, including four held-out tasks, demonstrate that our 4B-parameter agent matches or surpasses state-of-the-art baselines using much larger models, while requiring significantly fewer evaluations. Model and inference scaling analysis further reveals that AHD Agent offers an effective trajectory toward truly autonomous heuristic design.