CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization
Weiwei Sun, Shengyu Feng, Shanda Li, Yiming Yang · 2025
Read CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization by Weiwei Sun, Shengyu Feng, Shanda Li, Yiming Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04310.txt.
Introduction
Weiwei Sun and co-authors build a testbed for language-model agents that design algorithms. Their focus is combinatorial optimization: hard routing, packing, and scheduling puzzles with strict constraints. Progress here has lagged other fields because no shared benchmark existed. CO-Bench fills the gap with 36 real-world problems across many domains and difficulty levels.
Each problem ships with a clean statement and curated data, so agents can be scored fairly. The team runs several agent frameworks against classic human-designed algorithms. The contests expose where agents shine, where they stumble, and which ideas look most promising. The benchmark is public, giving the field a common yardstick for a skill that industry leans on daily.
Catalog record
| CREATOR | Weiwei Sun, Shengyu Feng, Shanda Li, Yiming Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04310
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization Weiwei Sun, Shengyu Feng, Shanda Li, Yiming Yang Abstract 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 . Carnegie Mellon University {weiweis,shengyuf,shandal,yiming}@cs.cmu.edu Introduction Combinatorial Optimization (CO) is a foundational problem class in computer science and operation research, focused on finding optimal solutions in discrete, structured, and constraint-rich domains. It underpins a wide range of real-world applications, including logistics ( Vogiatzis and Pardalos 2013 ) , production planning ( Crama 1997 ) , bioinformatics ( Gusfield 1997 ) , etc. Many CO problems are computationally intractable and classified as NP-hard, making exact solutions impractical at scale. As a result, developing effective algorithms often demands significant domain expertise and manual effort—posing a long-standing challenge in both academic research and industrial applications. Figure 1: Overview of CO-Bench. CO-Bench includes 36 problems from 8 categories, and aims to evaluate LLM agents’ ability to develop effective and efficient algorithms for solving real-world combinatorial optimization problems. Recent advances in Large Language Models (LLMs) ( OpenAI 2024b ; DeepSeek-AI 2025a ) have positioned LLM-based agents as increasingly promising tools for a variety of prediction and decision-making tasks ( Jimenez et al. 2023 ; Chan et al. 2024 ; Gottweis et al. 2025 ) . In particular, there is growing interest in applying LLMs to CO problems. Initial investigations have largely focused on solution correctness, evaluated on small-scale test instances ( Ramamonjison et al. 2023 ; Yang et al. 2025a ; Xiao et al. 2024a ) , and are often geared towards solving problems posed by general users. More recent works have begun to explore autonomous LLM agents capable of conducting research and designing more efficient algorithms for complex scientific and industrial challenges. For example, FunSearch ( Romera-Paredes et al. 2023 ) combines LLM prompting with evolutionary search to discover heuristics that outperform human-designed counterparts in the Cap Set and Bin Packing problems. Subsequent methods ( Liu et al. 2024 ; Ye et al. 2024 ; Novikov et al. 2025 ) further improve computational efficiency and broaden applicability to domains such as routing and scheduling. Despite these advancements, most existing efforts focus on narrow components (e.g., priority functions) within established algorithms, across a limited set of tasks (typically 4-7 problems), and often rely on heavily handcrafted, problem-specific prompts and templates ( Romera-Paredes et al. 2023 ; Ye et al. 2024 ) . Furthermore, there remains a lack of systematic evaluation of how these agents perform across a broader and more diverse collection of real-world CO problems. To address this gap, we introduce CO-Bench , a comprehensive benchmark designed to evaluate LLM agents in the context of efficient CO algorithm development. CO-Bench comprises real-world CO problems spanning a wide range of domains and complexities. Figure 1 illustrates the problem categories and examples, while Table 1 compares CO-Bench with existing CO benchmarks. Compared to prior benchmarks, CO-Bench offers broader problem coverage, and emphasizes end-to-end evaluation of LLM-based research agents, focusing on their ability to design efficient, potentially novel algorithms from abstract problem descriptions . This design enables reproducible and scalable evaluation of agent performance, including comparisons with human-designed classical CO solver under equivalent time constraints. By doing so, CO-Bench introduces new challenges for LLM agent development, such as the discovery of algorithms that extend beyond current human knowledge of CO. Using CO-Bench, we benchmark 15 LLMs and 9 agentic frameworks, comparing their performances against both human-designed classical algorithms and the best-known solutions reported in the literature. Our results show that reasoning models (e.g., o3-mini and Claude-3.7-sonnet) consistently outperform standard no-reasoning LLMs. When integrated into agentic frameworks like FunSearch, LLMs further improve through trial-and-error exploration. Notably, on 25 problems, LLM-generated algorithms outperformed classical solvers, and on 3 problems, they surpassed the best-known solutions. However, our analysis also reveals current limitations, such as limited algorithmic novelty and insufficient handling of feasibility constraints. These findings highlight both the promise and challenges of LLM-driven research in CO and suggest key directions for advancing autonomous algorithm design. In summary, this paper makes the following contributions: (i) We introduce CO-Bench, the first comprehensive benchmark to evaluate the capability of LLMs to develop algorithms for diverse and challenging real-world CO problems (ii) We benchmark 15 LLMs and 9 agentic frameworks, analyzing their performance relative to expert-designed pipelines. Our results highlight the strengths of agent-generated algorithms, while also revealing limitations in planning, feasibility checking, and the generation of efficient solution. Preliminary Combinatorial Optimization For each CO problem c (for example, Traveling salesman problem), we follow Papadimitriou and Steiglitz (1982) to formulate it as a constrained optimization problem in the discrete space. Consider an instance p , the optimization problem could be expressed as \min_{x\in S_{c}(p)}f_{c}(x;p)+g_{c}(x;p), (1) where S_{c}(p) represents the solution space, e.g., \mathbf{Z}^{m}\times\mathbb{R}^{n} for d discrete variables and n continuous variables, f_{c}(x;p) corresponds to the objective function, and g_{c}(x;p) stands for the constraint violation, which is 0 for feasible solutions and +\infty otherwise. To avoid the clutter, we simply denote h_{c}(x;p)=f_{c}(x;p)+g_{c}(x;p) in the following text and omit c if the context is clear. Given an algorithm set \mathcal{A} and a problem instance distribution D , the algorithm search problem is defined as \min_{A\in\mathcal{A}}\mathbb{E}_{p\sim D,x\sim A(p)}[h(x;p)]. (2) In contrast to previous neural CO solvers ( Bengio, Lodi, and Prouvost 2020 ) that directly parameterize A with a neural network, we focus on symbolic searching space where \mathcal{A} consists of all algorithms that could be represented by a Python Program, with a maximum number of d tokens, where d is typically decided by the output length limit of an LLM. Considering the popularity of randomized algorithms ( Motwani and Raghavan 2013 ) for CO, we treat the output of an algorithm A(p) as a distribution of solutions, while deterministic algorithms would correspond to the point distributions. The main endeavor of this work is focused on the shaping of the algorithm set \mathcal{A} , the curation of the data distribution D and the definition of h on our collected CO problems. Dataset Algorithm Dev Problem Num Instance Num Largest Variables NPHardEval ✗ 9 900 24 NL4OPT ✗ 5 289 3 OptiBench ✗ 4 605 18 ComplexOR ✗ 20 100 9 ReEvo ✓ 7 597 1,000 CO - Bench ✓ 36 6,482 11,000 Table 1: Data statistics for CO-Bench and related CO benchmarks, including the indicator for algorithm development support, the number of problem types, the number of test-set problem instances, and the largest number of test-set variables (e.g., the number of nodes in the largest graph). LLM Agents Given a CO