A tool-integrated, multi-turn LLM agent trained with reinforcement learning for automatic heuristic design.

---

✨ Highlights

🛠️ New Agentic Framework Proactively calls tools and uses feedback during heuristic generation.

🎯 Agentic RL Training Learns heuristic design from synthesized AHD environments across multiple domains.

⚡ Efficient & Generalizable A compact 4B agent outperforms larger-model baselines across diverse design settings.

---

🔁 Agent Loop

AHD Agent maintains an interaction history and makes state-dependent decisions over multiple turns. At each step, the agent can decide to:

1. 🧪 Generate or revise a candidate heuristic;
2. 📈 Evaluate the heuristic on a design set;
3. 🔍 Call tools to collect targeted feedback;
4. ✅ Continue refining or return the final heuristic.

AHD Agent workflow: the model iteratively uses feedback, tools, and evaluations to improve heuristics.

📊 Results

We evaluate AHD Agent across different settings, including constructive heuristics, ant-colony-optimization heuristics, held-out combinatorial domains, and cost-aware Bayesian optimization.

Efficient Design-Time Convergence

On RL training domains, the agent reaches competitive or superior gaps with only about 11–15 evaluator calls in the short setting.
The design-time convergence curves show that AHD Agent improves quickly under limited evaluation budgets and continues to benefit when the budget is expanded.

AHD Agent converges faster and achieves better performance under larger evaluation budgets.

Potential from Stronger Backbones

AHD Agent has strong potential to improve with stronger LLM backbones. Model scaling produces more consistent gains for the agentic multi-turn paradigm than for fixed-workflow AHD methods, suggesting that stronger reasoning ability is better converted into heuristic-design performance when the model controls the design process.

Performance improves as the backbone model becomes stronger.

Cross-Domain Generalization

The RL-trained agent generalizes beyond the domains used during training. As the number of RL training domains increases, performance improves not only on in-domain tasks but also on held-out domains, indicating that cross-domain RL training learns transferable heuristic-design behavior.

Held-out performance improves as the training mixture covers more domains.

Inference-Time Scaling

AHD Agent can also be enhanced at inference time by increasing the evaluator budget. Continuing one coherent multi-turn trajectory can be more effective than aggregating independent short trajectories, because later revisions can exploit accumulated feedback from earlier turns.

Sequential refinement benefits from accumulated feedback under larger evaluation budgets.

🔖 Citation

If you find our model, data, or evaluation code useful, please kindly cite our paper:

@article{lv2026ahdagent,
  title   = {AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design},
  author  = {Lv, Haoze and Lu, Ning and Zhou, Ziang and Liu, Shengcai},
  journal = {arXiv preprint arXiv:2605.08756},
  year    = {2026}
}

📬 Contact

For questions about the paper, please contact Shengcai Liu at liusc3@sustech.edu.cn.

---