# CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization

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

## Key facts

- Cited by 28 papers in the map (data through 7 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 27 of its 82 references that are in the map.
- First posted on arXiv 6 Apr 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, 27 of 27)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [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)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineering](https://mlsanity.com/paper/2410.07095/) (2024)
- [Accelerating scientific discovery with Co-Scientist](https://mlsanity.com/paper/2502.18864/) (2025)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [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)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [AIDE: AI-Driven Exploration in the Space of Code](https://mlsanity.com/paper/2502.13138/) (2025)
- [RE-Bench: Evaluating frontier AI R&D capabilities of language model agents against human experts](https://mlsanity.com/paper/2411.15114/) (2024)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling](https://mlsanity.com/paper/2407.09887/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Packing unequal rectangles and squares in a fixed size circular container using formulation space search](https://mlsanity.com/paper/1802.07519/) (2018)

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

- [Scaling Long-Horizon LLM Agent via Context-Folding](https://mlsanity.com/paper/2510.11967/) (2025)
- [CodePDE: An Inference Framework for LLM-driven PDE Solver Generation](https://mlsanity.com/paper/2505.08783/) (2025)
- [AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?](https://mlsanity.com/paper/2507.15887/) (2025)
- [AlphaOPT: Formulating Optimization Programs with Self-Improving LLM Experience Library](https://mlsanity.com/paper/2510.18428/) (2025)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization](https://mlsanity.com/paper/2602.02188/) (2026)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [CoMind: Towards Community-Driven Agents for Machine Learning Engineering](https://mlsanity.com/paper/2506.20640/) (2025)
- [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)
- [Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems](https://mlsanity.com/paper/2505.23881/) (2025)
- [DCP-Bench-Open: Evaluating LLMs for Constraint Modelling of Discrete Combinatorial Problems](https://mlsanity.com/paper/2506.06052/) (2025)
- [STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization](https://mlsanity.com/paper/2506.11057/) (2025)
- [Metan: Recursive Self-Improvement through Emergent Depth](https://mlsanity.com/paper/2608.24735/) (2026)
- [ReproRepo: Scaling Reproducibility Audits with GitHub Repository Issues](https://mlsanity.com/paper/2606.18237/) (2026)
- [Attacks and Defenses Against LLM Fingerprinting](https://mlsanity.com/paper/2508.09021/) (2025)
- [MCCE: A Framework for Multi-LLM Collaborative Search in Discrete Spaces with Similarity-Filtered Preference Learning](https://mlsanity.com/paper/2510.06270/) (2025)
- [Memory-Guided Tree Search with Cross-Branch Knowledge Transfer for LLM Solver Synthesis](https://mlsanity.com/paper/2605.17539/) (2026)
- [SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems](https://mlsanity.com/paper/2607.23676/) (2026)
- [ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search](https://mlsanity.com/paper/2608.15546/) (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)
- [ORAgentBench: Can LLM Agents Solve Challenging Operations Research Tasks End to End?](https://mlsanity.com/paper/2606.19787/) (2026)
- [RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search](https://mlsanity.com/paper/2606.31801/) (2026)
- [When Evidence Changes the Subject: Subject-Typed Claim Licensing for Learned Routing](https://mlsanity.com/paper/2609.33505/) (2026)

## Abstract (arXiv)

Although LLM-based agents have attracted significant attention in domains such as software engineering and machine learning research, their role in advancing combinatorial optimization (CO) remains relatively underexplored. This gap underscores the need for a deeper understanding of their potential in tackling structured, constraint-intensive problems -- a pursuit currently limited by the absence of comprehensive benchmarks for systematic investigation. To address this, we introduce CO-Bench, a benchmark suite featuring 36 real-world CO problems drawn from a broad range of domains and complexity levels. CO-Bench includes structured problem formulations and curated data to support rigorous investigation of LLM agents. We evaluate multiple agentic frameworks against established human-designed algorithms, revealing the strengths and limitations of existing LLM agents and identifying promising directions for future research. CO-Bench is publicly available at https://github.com/sunnweiwei/CO-Bench.