Research map / Multi-agent systems and games / LLM agents

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

AAAI 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent collaboration and safety · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces CO-Bench, a 36-problem benchmark for evaluating LLM agents that design algorithms (Python programs) for real-world combinatorial optimization problems, benchmarking 15 LLMs and 9 agentic frameworks against classical solvers.

Problem

Existing benchmarks for LLMs on combinatorial optimization either cover few problems, test only small-instance correctness, or do not evaluate end-to-end algorithm design efficiency; there is no comprehensive benchmark for assessing LLM agents' algorithm search on diverse real-world CO problems.

Approach

Frames CO as algorithm search over Python programs scored by normalized objective on dev/test instances under a time limit, with 36 curated OR-Library-based problems (manually annotated descriptions, load_data and eval_func), and compares agent-generated algorithms against well-tuned classical solvers and best-known solutions.

Key results

• FunSearch with o3-mini attains the highest average score of 0.842, above the classical solver's 0.797.
• Best one-shot LLM, Claude-3.7 Sonnet, reaches an average score of 0.65 under direct generation.
• The best agents reach a valid solution rate of 0.555, below the classical solver's 0.611.

Surprising findings

• Advanced agent AIDE underperforms simple BestOfN sampling on most metrics despite higher valid-solution rates.
• Agent-generated algorithms increasingly rely on general-purpose solvers (ortools, pulp, scipy) over time, reaching 25% of problems at 64 steps.

Limitations

• Agents struggle with feasibility and constraint satisfaction, with valid solution rates below the classical solver.
• Generated algorithms show limited novelty, mostly applying established techniques.
• Performance saturates after about 30 search steps.

Experimental setup

Datasets: OR-Library

Benchmarks: CO-Bench

Metrics: Avg Score Valid Solution Above Classical Survival Rate

Baselines: Classical solver (human-designed) BestOfN Chain of Experts Greedy Refinement FunSearch EoH AIDE ReEvo MSTC-AHD DIMES DIFUSCO T2T

Builds on: FunSearch EoH ReEvo AIDE Chain of Experts

Closest papers by meaning

• $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization (NeurIPS 2025 · similarity 0.89)
• Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.89)
• GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.88)
• AgentSwift: Efficient LLM Agent Design via Value-Guided Hierarchical Search (AAAI 2026 · similarity 0.88)
• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
• MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework (AAAI 2026 · similarity 0.87)