# RoCo: Role-Based LLMs Collaboration for Automatic Heuristic Design

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 3 Dec 2025.

## Builds on (most cited first, 14 of 14)

- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors](https://mlsanity.com/paper/2308.10848/) (2023)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [Multi-Agent Collaboration: Harnessing the Power of Intelligent LLM Agents](https://mlsanity.com/paper/2306.03314/) (2023)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Exploring Collaboration Mechanisms for LLM Agents: A Social Psychology View](https://mlsanity.com/paper/2310.02124/) (2023)
- [Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents](https://mlsanity.com/paper/2403.02502/) (2024)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Large Language Model-Based Evolutionary Optimizer: Reasoning with elitism](https://mlsanity.com/paper/2403.02054/) (2024)

## Abstract (arXiv)

Automatic Heuristic Design (AHD) has gained traction as a promising solution for solving combinatorial optimization problems (COPs). Large Language Models (LLMs) have emerged and become a promising approach to achieving AHD, but current LLM-based AHD research often only considers a single role. This paper proposes RoCo, a novel Multi-Agent Role-Based System, to enhance the diversity and quality of AHD through multi-role collaboration. RoCo coordinates four specialized LLM-guided agents-explorer, exploiter, critic, and integrator-to collaboratively generate high-quality heuristics. The explorer promotes long-term potential through creative, diversity-driven thinking, while the exploiter focuses on short-term improvements via conservative, efficiency-oriented refinements. The critic evaluates the effectiveness of each evolution step and provides targeted feedback and reflection. The integrator synthesizes proposals from the explorer and exploiter, balancing innovation and exploitation to drive overall progress. These agents interact in a structured multi-round process involving feedback, refinement, and elite mutations guided by both short-term and accumulated long-term reflections. We evaluate RoCo on five different COPs under both white-box and black-box settings. Experimental results demonstrate that RoCo achieves superior performance, consistently generating competitive heuristics that outperform existing methods including ReEvo and HSEvo, both in white-box and black-box scenarios. This role-based collaborative paradigm establishes a new standard for robust and high-performing AHD.